1054 - Efficient Pseudo Code

Time Limit: 1 second(s)

Memory Limit: 32 MB

Sometimes it's quite useful to write pseudo codes for problems. Actually you can write the necessary steps to solve a particular problem. In this problem you are given a pseudo code to solve a problem and you have to implement the pseudo code efficiently. Simple! Isn't it? :)

pseudo code

{

take two integers n and m

let p = n ^ m (n to the power m)

let sum = summation of all the divisors of p

let result = sum MODULO 1000,000,007

}

Now given n and m you have to find the desired result from the pseudo code. For example if n = 12 and m = 2. Then if we follow the pseudo code, we get

pseudo code

{

take two integers n and m

so, n = 12 and m = 2

let p = n ^ m (n to the power m)

so, p = 144

let sum = summation of all the divisors of p

so, sum = 403, since the divisors of p are 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 36, 48, 72, 144

let result = sum MODULO 1000,000,007

so, result = 403

}

Input

Input starts with an integer T (≤ 5000), denoting the number of test cases.

Each test case will contain two integers, n (1 ≤ n) and m (0 ≤ m). Each of n and m will be fit into a 32 bit signed integer.

Output

For each case of input you have to print the case number and the result according to the pseudo code.

Sample Input

Output for Sample Input

12 2

12 1

36 2

Case 1: 403

Case 2: 28

Case 3: 3751

PROBLEM SETTER: JANE ALAM JAN

思路：先打表素数，然后我们先将每个x分解成各个质因数的和，然后我们知道sum=（p1⁰+p1¹+...p1^r1）*(p2⁰+p2¹+....p2^r2)*...

pi为质因数，ri为每个质因数的个数乘以y，那么每项用等比数列求和公式求下，然后（1-q^r+1）/（1-q）;然后费马小定理求下逆元即可。

  1 #include<stdio.h>

  2 #include<algorithm>

  3 #include<iostream>

  4 #include<string.h>

  5 #include<stdlib.h>

  6 #include<queue>

  7 #include<stack>

  8 using namespace std;

  9 bool prime[1000000];

 10 int ans[1000000];

 11 int mod=1e9+7;

 12 typedef  long long LL;

 13 typedef struct pp

 14 {

 15     int x;

 16     int y;

 17 } ss;

 18 ss sum[1000];

 19 stack<ss>que;

 20 LL quick(LL n,LL m);

 21 int main(void)

 22 {

 23     memset(prime,0,sizeof(prime));

 24     int i,j,k;

 25     for(i=2; i<=1000; i++)

 26     {

 27         if(!prime[i])

 28         {

 29             for(j=i; (i*j)<=1000000; j++)

 30             {

 31                 prime[i*j]=true;

 32             }

 33         }

 34     }

 35     int cnt=0;

 36     for(i=2; i<=1000000; i++)

 37     {

 38         if(!prime[i])

 39         {

 40             ans[cnt++]=i;

 41         }

 42     }

 43     scanf("%d",&k);

 44     int s;

 45     LL x,y;

 46     for(s=1; s<=k; s++)

 47     {

 48         scanf("%lld %lld",&x,&y);

 49         int tt=0;

 50         int id=0;

 51         int an=0;

 52         while(x>1&&tt<cnt)

 53         {

 54             if((LL)ans[tt]*(LL)ans[tt]>x)

 55             {   if(an!=0)

 56             {

 57                 ss dd;

 58                 dd.x=ans[tt];

 59                 dd.y=an;

 60                 que.push(dd);

 61                 an=0;

 62             }

 63                 break;

 64             }

 65             else  if(x%ans[tt]==0)

 66             {

 67                 an++;

 68                 x/=ans[tt];

 69                 if(x==1)

 70                 { ss dd;

 71                 dd.x=ans[tt];

 72                 dd.y=an;

 73                 que.push(dd);

 74                 an=0;

 75                 }

 76             }

 77             else if(x%ans[tt]!=0)

 78             {

 79                 if(an!=0)

 80                 {

 81                     ss ask;

 82                     ask.x=ans[tt];

 83                     ask.y=an;

 84                     que.push(ask);

 85                     an=0;

 86                 }

 87                 tt++;

 88             }

 89         }

 90         if(!que.empty())

 91         {

 92             ss ap=que.top();

 93             if(x!=1)

 94             {

 95                 if(x!=ap.x)

 96                 {

 97                     ss ask;

 98                     ask.x=x;

 99                     ask.y=1;

100                     que.push(ask);

101                 }

102                 else

103                 {

104                     ss dd=que.top();

105                     que.pop();

106                     dd.y+=1;

107                     que.push(dd);

108                 }

109             }

110         }

111         else

112         {

113

114             if(x!=1)

115             {

116                     ss ask;

117                     ask.x=x;

118                     ask.y=1;

119                     que.push(ask);}

120

121         }

122         int vv=0;

123         while(!que.empty())

124         {

125             sum[vv]=que.top();

126

127             que.pop();

128             vv++;

129         }

130         LL ac=1;

131         for(i=0; i<vv; i++)

132         {

133             //printf("%d %d\n",sum[i].x,sum[i].y);

134             LL q=sum[i].x-1;

135             LL ni=quick((LL)q,(LL)(mod-2));

136             LL r=(sum[i].y*y+1)%(mod-1);

137             LL p=quick((LL)sum[i].x,(LL)(r));

138             p-=1;

139             p=(p%mod+mod)%mod;

140             p=p*ni%mod;

141             ac=ac*p%mod;

142         }

143         printf("Case %d:",s);

144         printf(" %lld\n",ac%mod);

145     }

146     return 0;

147 }

148 LL  quick(LL n,LL m)

149 {

150     LL ak=1;

151     n%=mod;

152     while(m)

153     {

154         if(m&1)

155         {

156             ak=(ak%mod)*(n%mod)%mod;

157         }

158         n=(n*n)%mod;

159         m/=2;

160     }

161     return ak;

162 }

巴特西

1054 - Efficient Pseudo Code

Input

Output

Sample Input

Output for Sample Input

最新文章

热门文章