数论题求调

题目大意： 给定

A

B

，求

A^B

的约数和

S

模

P = 10^9 + 7

。

A \leq 10^{12}, B\leq 10^{18}

。（洛谷上没找到原题）

思路： 令

A = \prod_{i=1}^n a_i^{p_i}

，则

A^B = \prod_{i=1}^n a_i^{Bp_i}

A^B

的约数和为

S = \prod_{i=1}^n \left( \sum_{j=0}^{Bp_i} a_i^j \right) = \prod_{i=1}^n \left(\frac{a_i^{Bp_i+1} - 1}{a_i - 1}\right)

用乘法逆元和欧拉定理（忘了是不是这个名字）得

S \equiv \prod_{i=1}^n \left( (a_i^{Bp_i+1 \bmod \varphi(P)} - 1)(a_i - 1)^{-1} \right) \pmod P

代码：

CPP

#include<bits/stdc++.h>
using namespace std;

#define ll unsigned long long

const ll MAXFAC=45;
const ll MOD=1e9+7;

ll a,b;
ll afact[MAXFAC],afactpow[MAXFAC],afactcnt=1;

ll qpow(ll a,ll b){
    ll base=a,ans=1ll;
    while(b){
        if(b&1)
            (ans*=base)%=MOD;
        (base*=base)%=MOD;
        b>>=1;
    }
    return ans;
}

int main(){
    ll i,j;
    freopen("sumdiv.in","r",stdin);
    freopen("sumdiv.out","w",stdout);
    cin>>a>>b;
    ll newb=b%(MOD-1);
    for(i=2;i*i<=a;i++){
        if(a==1)
            break;
        
        bool flag=0;
        while(a%i==0){
            if(!flag){
                flag=1;
                afact[afactcnt]=i;
                afactpow[afactcnt]=1;
            }
            else
                afactpow[afactcnt]++;
            a/=i;
        }
        if(flag)
            afactcnt++;
    }
    if(a>1){
        afact[afactcnt]=a;
        afactpow[afactcnt]=1;
        afactcnt++;
    }
    
    //for(i=1;i<afactcnt;i++)
    //   cout<<afact[i]<<' '<<afactpow[i]<<endl;

    ll ans=1;
    for(i=1;i<afactcnt;i++){
        ll afapow=(newb*afactpow[i]+1)%(MOD-1);
        
        (ans*=(qpow(afact[i],afapow)-1+MOD))%=MOD;
        (ans*=qpow(afact[i]-1,MOD-2))%=MOD;
    }
    cout<<ans<<endl;
    return 0;
}

目前 79 分（WA）

讨论操作

回复

相关推荐

数论题求调