HDU 1452 Happy 2004 (逆元+快速幂+积性函数)

G - Happy 2004

Time Limit:1000MS     Memory Limit:32768KB     64bit IO Format:%I64d & %I64u

Description

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

1
10000
0
 

Sample Output

6
10
题意:
求2004的x次幂的因子和并对29取余。
题解:

6的因子是1,2,3,6; 6的因子和是 s(6)=1+2+3+6=12;

20的因子是1,2,4,5,10,20; 20的因子和是 s(20)=1+2+4+5+10+20=42;

2的因子是1,2; 2的因子和是 s(2)=1+2=3;

3的因子是1,3; 3的因子和是 s(3)=1+3=4;

4的因子和是 s(4)=1+2+4=7;

5的因子和是 s(5)=1+5=6;

s(6)=s(2)*s(3)=3*4=12;

s(20)=s(4)*s(5)=7*6=42;

这是巧合吗?

再看 s(50)= 1+2+5+10+25+50=93=3*31=s(2)*s(25),s(25)=1+5+25=31.

这在数论中叫积性函数,当gcd(a,b)=1时 s(a*b)=s(a)*s(b);

具体的证明过程请看我之前的博客:传送门

如果p是素数

s(p^n)=1+p+p^2+...+p^n= (p^(n+1)-1) /(p-1) (1)

计算 因子和 s(2004^X) mod 29 ,

2004=2^2 *3 *167

s(2004^X) ) = (s(2^2X))) * (s(3^X))) * (s(167^X)))

167)=22;

s(2004^X) ) = (s(2^2X))) * (s(3^X))) * (s(22^X)))

a=s(2^2X)=(2^(2X+1)-1) //根据 (1)

b=s(3^X)= (3^(X+1)-1)/2 //根据 (1)

c=s(22^X)= (22^(X+1)-1)/21 //根据 (1)

%运算法则 1. (a*b) %p= ( a%p) *(b%p)

%运算法则 2. (a/b) %p= ( a *b^(-1)%p)

b^(-1)是 b的逆元素 (%p)可以用扩展欧几里德逆元模板求

2的逆元素是15 ()) ,因为2*15=30 % 29=1 % 29

21的逆元素是18 ()) ,因为21*18=378% 29 =1 % 29

因此

a=(powi(2,2*x+1,29)-1)% 29;

b=(powi(3,x+1,29)-1)*15 % 29;

c=(powi(22,x+1,29)-1)*18 % 29;

ans=(a*b)% 29*c % 29;

#include <iostream>
using namespace std;
typedef long long ll;
const int mod=;
ll pow(ll a,ll b)
{
ll ans=;
while(b)
{
if(b&)
ans=ans*a%mod;
b>>=;
a=a*a%mod;
}
return ans;
}
int main()
{
int x;
while(cin>>x&&x)
{
ll a=(pow(,*x+)-+mod)%mod;
ll b=(pow(,x+)-+mod)*%mod;
ll c=(pow(,x+)-+mod)*%mod;
ll ans=a*b*c%mod;
cout<<ans<<endl;
}
return ;
}
上一篇:android LinearLayout添加分隔线


下一篇:Android onTouchEvent, onClick及onLongClick的调用机制