题目大意: 给定 A,B,求 AB 的约数和 S 模 P=109+7。A≤1012,B≤1018。(洛谷上没找到原题)
思路: 令 A=∏i=1naipi,则 AB=∏i=1naiBpi AB 的约数和为 S=∏i=1n(∑j=0Bpiaij)=∏i=1n(ai−1aiBpi+1−1) 用乘法逆元和欧拉定理(忘了是不是这个名字)得 S≡∏i=1n((aiBpi+1modφ(P)−1)(ai−1)−1)(modP)
代码:
#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)