本文共 3363 字，大约阅读时间需要 11 分钟。

 

Consider a positive integer X,and let S be the sum of all positive integer divisors of 2004^X. Your job is to determine S modulo 29 (the rest of the division of S by 29). 

Take X = 1 for an example. The positive integer divisors of 2004^1 are 1, 2, 3, 4, 6, 12, 167, 334, 501, 668, 1002 and 2004. Therefore S = 4704 and S modulo 29 is equal to 6. 

Input

The input consists of several test cases. Each test case contains a line with the integer X (1 <= X <= 10000000). 

A test case of X = 0 indicates the end of input, and should not be processed. 

Output

For each test case, in a separate line, please output the result of S modulo 29. 

Sample Input

1100000

Sample Output

610

 题意就是给一个数x，求2004的x次方的约数之和。

2004有三个素约数，2，3，167.  167mod29=22，可以把167换成22.

因为有 S(p^n)=1+p+p^2+...p^n=(p^(n+1)-1)/(p-1) 所以本题 就可以S(2004^x)=(2^(2*x+1)-1)(3^(x+1)-1)/2*(167^(x+1)-1)/166

因为（1*2*166）与 29 互质，所以不会影响答案，直接用上面的公式做就好了。

#include 
   
      using namespace std;     int main()  {      int n;      while (cin>>n && n!=0)      {  		n%=28;	int r,f,t,d;      f=t=d=1;      for (r=0;r<=n;++r)      {          f=f*(r==n?2:4)%29;           t=t*3%29;                        d=d*22%29;                  }           r=(f-1)*(t-1)*(d-1)%29;             int ans= r*9%29;        cout<
    
     <
    
   

As we all know, the next Olympic Games will be held in Beijing in 2008. So the year 2008 seems a little special somehow. You are looking forward to it, too, aren't you? Unfortunately there still are months to go. Take it easy. Luckily you meet me. I have a problem for you to solve. Enjoy your time.

Now given a positive integer N, get the sum S of all positive integer divisors of 2008N. Oh no, the result may be much larger than you can think. But it is OK to determine the rest of the division of S by K. The result is kept as M.

Pay attention! M is not the answer we want. If you can get 2008M, that will be wonderful. If it is larger than K, leave it modulo K to the output. See the example for N = 1，K = 10000: The positive integer divisors of 20081 are 1、2、4、8、251、502、1004、2008，S = 3780, M = 3780, 2008M % K = 5776. 

 

Input

The input consists of several test cases. Each test case contains a line with two integers N and K (1 ≤ N ≤ 10000000, 500 ≤ K ≤ 10000). N = K = 0 ends the input file and should not be processed.  

Output

For each test case, in a separate line, please output the result.  

Sample Input

1 10000 0 0  

Sample Output

5776 这题是类似的一题，可以除法可以通过求逆元。因为上面题的mod是29，gcd(2*166,29)==1，存在逆元。但是这里的gcd(250,k)不一定满足等于1，也就是说不一定存在逆元。

那么观察我们要求的m，m肯定有250这个分母，所以可以表示成m=x/250。m%k=(x/250)%k转化为(x%(250*k))/250。求变成了先除法再取余了。

#include
   
    #define LL long longusing namespace std;const int N = 100000 + 5;LL n,k,a,b,ans;LL chong(LL a,LL b,LL mod){	LL ans=1;	while(b){		if(b%2==1)		ans=(ans*a)%mod;		b>>=1;		a=(a*a)%mod;	}	return ans;} int main(){	while(cin>>n>>k){		if(n==0&&k==0){			break;		}		a=chong(2,3*n+1,250*k);		b=chong(251,n+1,250*k);		a--,b--;		ans=(a*b)%(250*k);		ans/=250;		ans=((ans%k)+k)%k;		cout<
    
     <
    
   

本周做的几道题全是和素数，约数求和有关的。我还是把约数求和的模型给自己再写一遍。

#include 
   
    #include 
    
     #include 
     
      # typedef long int llconst int size= 10000;const int mod = 29;ll sum(ll p,ll n);ll power(ll p,ll n);using namespace std;int main(){	int A,B;	int p[size];	int n[size];	while(cin>>A>>B)	{		int i,k=0;		for(i=2;i*i
      
       0)	{		if(n%2)			sq=(sq*p)%mod;		n/=2;		p=p*p%mod;	}	return sq;}