HDU1452 Happy 2004（逆元+约数和定理）

HDU - 1452 Happy 2004

Problem 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

题解

题意

给定一个大于等于1，小于等于10000000的数X，让你给出2004^X的所有因子和，鉴于值比较大，MOD上一个29.

思路

因子和实际上是一个积性函数，什么是积性函数呢？
积性函数就是满足S(a*b) = S(a) * S(b)条件的函数。
为什么因子和满足这个条件呢。例如给定数m可以质因数分解为m=a*b;于是有:
​ S(a) = (1+a) ,S(b)= (1+b);
​ S(a*b) = (1+a+b+a*b) = S(a)*S(b);
所以可见因子和函数是一个积性函数

我们将2004进行质因数分解后可以得到2004 = (2^2)*3*167
约数和定理：sum=(p1^0+...+p1c1)*(p2^0+...+p2c1)*...*(pk^0+...+pkck)。每一项可以通过等比数列求和得到。所以答案就是2^(2*n+1)*3(n+1)*167^(n+1)/(2*166)。由于需要取余，所以不能直接除要求出2*166的逆元改为相乘。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
int T;

const int mod = 29;

void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
	if(!b){ d=a;x=1;y=0;	}
	else{
		exgcd(b,a%b,d,y,x); y-=x*(a/b);	
	}
}

ll inv(ll a,ll b){
	ll d,x,y;
	exgcd(a,b,d,x,y);
	return d==1?(x+b)%b:-1;
}

int fast_power(int a,int b,int mod){
	int ans = 1;
	while(b){
		if((b&1))ans=ans*a%mod;
		a = a*a%mod;
		b >>=1;
	}
	return ans;
}


int main() {
	int i1 = inv(1,mod);
	int i2 = inv(2,mod);
	int i3 = inv(166,mod);
	ll n,ans,a,b,c;
	//printf("%d %d %d
",i1,i2,i3);
	while(~scanf("%lld",&n)){
		if(n==0)	break;
		a=(fast_power(2,2*n+1,mod)-1)%mod;
		b=(fast_power(3,n+1,mod)-1)%mod;
		c=(fast_power(167,n+1,mod)-1)%mod;
		ans=((a*b*c*i2*i3)%mod+mod)%mod;
		printf("%d
",ans); 
	}
	
    return 0;
}