poj_1845

源地址：http://poj.org/problem?id=1845

题目大意就是给你A,B两个数，求A^B所有因子的和。

要解这道题目，那么就要先知道好几个知识点。

1.对于一个整数A，它有唯一的分解性，即它能被分解成其质因子幂的乘积：

A=p1^k1*p2^k2*p3^k3*p4*k4........pn^kn(其中pi是A的质因子)

2.对于一个已经分解为A=p1^k1*p2^k2*p3^k3*p4*k4........pn^kn的整数A，其所有的因子的和为：

Sum=(1+p1+p1^2+...p1^k1)*(1+p2+p2^2+p2^3+....p2^k2)+......(1+pn+pn^2+pn^3+......pn^kn)

__int64 sum(__int64 p,__int64 n)  //递归二分求 (1 + p + p^2 + p^3 +...+ p^n)%mod

{                          //奇数二分式 (1 + p + p^2 +...+ p^(n/2)) * (1 + p^(n/2+1))

    if(n==0)               //偶数二分式 (1 + p + p^2 +...+ p^(n/2-1)) * (1+p^(n/2+1)) + p^(n/2)

        return 1;

    if(n%2)  //n为奇数,

        return (sum(p,n/2)*(1+power(p,n/2+1)))%mod;

    else     //n为偶数

        return (sum(p,n/2-1)*(1+power(p,n/2+1))+power(p,n/2))%mod;

}

知道了以上这三点，就不难解决这道题目。

我们把A的所有质因子及其幂次全部拆解出来，注意A可能最后也是个质数，要考虑在内。

拆解以后，我们求得是A^B的所有因子和，那么上面的式子就变形为：

Sum=(1+p1+p1^2+...p1^(k1*B))*(1+p2+p2^2+p2^3+....p2^(k2*B))+......(1+pn+pn^2+pn^3+......pn^(kn*B))

带到模板里去计算即可。

#include<stdio.h>
#include<iostream>
#include<string>
#include<string.h>
#include<algorithm>
#include<iomanip>
#include<vector>
#include<time.h>
#include<queue>
#include<stack>
#include<iterator>
#include<math.h>
#include<stdlib.h>
#include<limits.h>
#include<set>
#include<map>
//#define ONLINE_JUDGE
#define eps 1e-8
#define INF 0x7fffffff
#define FOR(i,a) for((i)=0;i<(a);(i)++)
#define MEM(a) (memset((a),0,sizeof(a)))
#define sfs(a) scanf("%s",a)
#define sf(a) scanf("%d",&a)
#define sfI(a) scanf("%I64d",&a)
#define pf(a) printf("%d\n",a)
#define pfI(a) printf("%I64d\n",a)
#define pfs(a) printf("%s\n",a)
#define sfd(a,b) scanf("%d%d",&a,&b)
#define sft(a,b,c)scanf("%d%d%d",&a,&b,&c)
#define for1(i,a,b) for(int i=(a);i<b;i++)
#define for2(i,a,b) for(int i=(a);i<=b;i++)
#define for3(i,a,b)for(int i=(b);i>=a;i--)
#define MEM1(a) memset(a,0,sizeof(a))
#define MEM2(a) memset(a,-1,sizeof(a))
const double PI=acos(-1.0);
template<class T> T gcd(T a,T b){return b?gcd(b,a%b):a;}
template<class T> T lcm(T a,T b){return a/gcd(a,b)*b;}
template<class T> inline T Min(T a,T b){return a<b?a:b;}
template<class T> inline T Max(T a,T b){return a>b?a:b;}
using namespace std;
#define ll long long
int n,m;
#define Mod 1000000007
#define N 510
#define M 1000100
const int size = 46340+4;
const int mod = 9901;
int p;
ll prm[10010];
ll num[10010];
ll A,B;
ll power(ll p,ll n){
	ll res=1;
	while(n){
		if(n&1)
		res = (res*p)%mod;
		p = p*p%mod;
		n>>=1;
	}
	return res;
}
ll Sum(ll p,ll n){
	if(n == 0)
		return 1;
	if(n%2)
		return (Sum(p,n/2)*(1+power(p,n/2+1)))%mod;
	else
		return (Sum(p,n/2-1)*(1+power(p,n/2+1))+power(p,n/2))%mod;
}
int main(){
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
//  freopen("out.txt","w",stdout);
#endif

    while(scanf("%I64d%I64d",&A,&B)!=EOF){
    	memset(prm,0,sizeof prm);
    	memset(num,0,sizeof num);
    	int p=0;
    	for(ll i=2;i*i<=A;){
    		if(A%i==0){
    			prm[p] = i;
    			num[p]=0;
    			while(A%i==0){
    				num[p]++;
    				A /= i;
    			}
    			p++;
    		}
    		if(i==2) i++;	//
    		else i+=2;	//跳过偶数
    	}
    	if(A != 1){	//最后A整除的只剩下其本身为质数
    		prm[p] = A;
    		num[p]++;
    		p++;
    	}
    	ll ans = 1;
    	for(int i=0;i<p;i++){
    		ans = (ans*Sum(prm[i],num[i]*B))%mod;
    	}
    	printf("%I64d\n",ans%mod);
    }
return 0;
}