POJ 1845

接下来交给大家一个网上查不到的解题方法

题目是酱找出a^b的因子的和答案对9901取模

我们将a可变成这样e1^x1*e2^x2...（ei为素数）

答案就变成这样(e1^0+e1^1...e1^x1)*(e2^0+e2^1...e2^x2)...

利用同余模定理我们可以知道每个e都能变成e%9901

我们知道在e1^9900次幂为一，令9900为e1生成的循环群的幂数，我们可以知道(e1^0+e1^1...e1^9900)*(e1-e) = 0

所以可以将x1,x2...都模9900

over~

#include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
//#define __int64 long long
const __int64 mod = 9901;
__int64 ss(__int64 a, __int64 b){
    a %= mod;
    if(a == 0)return 1;
    if(a == 1) return b+1;
    b = b % (mod-1);
    __int64 ans = 0;
    __int64 m = 1;
    for(__int64 i =0 ;i <= b; i++){
        ans += m % mod;
        ans %= mod;
        m = (m*a)%mod;
    }
    return ans;
}

int main(){
    //freopen("in.cpp", "r", stdin);
    //freopen("out1.cpp", "w", stdout);
    __int64 a, b;
    while(cin>>a>>b){
        if(a == 0 ){printf("0
");continue;}
        __int64 ans = 1;
        for(__int64 i = 2; i*i <= a; i++){
            __int64 k = 0;
            while(a%i == 0){
                a/= i;
                k ++;
            }
            ans = (ans * ss(i, k*b))%mod;
        }
        if(a > 1)
            ans = (ans * ss(a,b))%mod;
        cout<<ans<<endl;
    }
}