- #include<bits/stdc++.h>
- using namespace std;
- #define srt 65540
- #define mod 1000000007
- typedef long long ll;
- ll prime[srt];
- ll k,t;
- void seive()
- {
- bool ara[srt];
- memset(ara,0,sizeof(ara));
- for(int i=2,k=0;i<srt;i++){
- if(ara[i]==0){
- prime[k++]=i;
- for(int j=i;j<srt;j=i+j)
- ara[j]=1;
- }
- t=k;
- }
- }
- ll Pow (ll x,ll y)
- {
- ll number = 1;
- while (y>0)
- {
- if (y % 2==1){
- number = (number * x) % mod;
- }
- x = (x * x) % mod;
- y>>=1;
- }
- return number;
- }
- ll sum(ll a,ll b)
- {
- ll total,res;
- res=(Pow(a,b)-1)%mod;
- res=(res*Pow(a-1,mod-2))%mod;
- return (res+mod)%mod;//to avoid negative numbers
- }
- int main()
- {
- ll n,m,cnt,num,T,l=0,total;
- cin>>T;
- seive();
- while(T--){
- scanf("%lld%lld",&n,&m);
- total=1;
- for(int i=0;i<t;i++){
- cnt=0;
- num=0;
- if(n%prime[i]==0){
- num=prime[i];
- while(n%prime[i]==0){
- n/=prime[i];
- cnt++;
- }
- total=(total*sum(num,cnt*m+1))%mod;
- }
- }
- if(n!=1){
- total=(total*sum(n,m+1))%mod;
- }
- printf("Case %lld: %lld\n",++l,total);
- }
- return 0;
- }
- /*
- #include <bits/stdc++.h>
- using namespace std;
- #define M 1000000007
- #define N 66000
- #define ll long long int
- vector<int> primes;
- bool sieve[N];
- void pre(){
- memset(sieve, true, sizeof(sieve));
- for(ll i = 2; i <N; i++){
- if(sieve[i]) primes.push_back(i);
- for(ll j = 2*i;j <N; j+=i){
- sieve[j] = false;
- }
- }
- //for(int i = 0; i <primes.size(); i++) cout<<primes[i]<<" ";
- }
- ll bigmod(ll p, ll q){
- if(q == 1) return p%M;
- if(q%2 == 0){
- ll a = bigmod(p, q/2);
- //cout<<"hdbfd";
- return ((a%M)*(a%M))%M;
- }
- else{
- //cout<<"hey";
- ll a = bigmod(p, q-1);
- return (a*p)%M;
- }
- }
- int main(){
- pre();
- int ts;
- cin>>ts;
- for(int l = 1; l <= ts; l++){
- int a, b;
- scanf("%d%d", &a, &b);
- ll ans = 1;
- int k = 0;
- while(a!=1){
- if(k == primes.size() || primes[k]>a) break;
- int c = 0;
- int p = primes[k];
- if(a%p == 0){
- while(a%p == 0){
- a/=p;
- c++;
- }
- ans = (ans*((bigmod((ll)p , (ll)c*b+1)-1+M)%M* (bigmod(p-1,M-2) + M)%M)%M)%M;
- ans = ans%M;
- }
- k++;
- }
- if(a!= 1){
- ans = ans * ((bigmod(a,b+1)-1+M)%M * (bigmod(a-1, M-2)+M)%M)%M;
- ans = ans%M;
- }
- printf("Case %d: %lld\n",l, ans);
- }
- return 0;
- }
- */
Friday 28 July 2017
Lightoj 1054 - Efficient Pseudo Code
Subscribe to:
Post Comments (Atom)
Most Featured Post
Lightoj 1159 - Batman
http://lightoj.com/volume_showproblem.php?problem=1159 problem analysis: First i thought of this as if s1, s2 and s3 are those three str...
-
Problem link: Problem Analysis: It is actually a basic Bisection problem , as we can see here we can not actually find a formula fo...
-
http://lightoj.com/volume_showproblem.php?problem=1382 Problem analysis: This is a rare problem i wrote about so far. After much strugg...
No comments:
Post a Comment