题目传送门
题意: 给你a,b,要你求ab的因子和对9901取模的结果。(1<=a<=5e7,0<=b<=5e7)
样例输入: 2
样例输出: 15
思路: 求因子,首先想到唯一分解定理,把a分解成最简形式,然后推式子得到a=(1+p1+p12+…+p1cnt1)*(1+p2+…+p2cnt2)…(1+pn+pn2+…pncntn),即等比数列求和之后相乘。
等比数列公式:Sn=a1*(qn-1)/(q-1) (q是公比,即提取出来的质因数)
因为过程中要取模,所以我们用快速幂求出qn,在除(q-1)的时候,要乘(q-1)在mod 9901 意义下的逆元,因为9901是个质数,所以我们可以用费马小定理进行求解。此题得解
得解个der: 如果我们有个质因子p,p%9901=1,那我们用费马小定理求逆元的时候,p-1%9901=0,这时候不存在逆元,所以会出错。那么试想,我们p%9901=1,那式子(1+p+p2+…+pcnt) 是不是就等于cnt+1?(因为里面每一项mod 9901之后都是1),所以计算的时候特判就行了。
代码:
#include<bits/stdc++.h>
#pragma GCC optimize("Ofast")
#define endl '\n'
#define null NULL
#define ls p<<1
#define rs p<<1|1
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ll long long
#define int long long
#define pii pair<int,int>
#define ull unsigned long long
#define all(x) x.begin(),x.end()
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define ct cerr<<"Time elapsed:"<<1.0*clock()/CLOCKS_PER_SEC<<"s.\n";
char *fs,*ft,buf[1<<20];
#define gc() (fs==ft&&(ft=(fs=buf)+fread(buf,1,1<<20,stdin),fs==ft))?0:*fs++;
inline int read(){int x=0,f=1;char ch=gc();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=gc();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=gc();}
return x*f;}
using namespace std;
const int N=1e5+5;
const int inf=0x3f3f3f3f;
const int mod=9901;
const double eps=1e-7;
const double PI=acos(-1);
vector<pii>v;
ll qpow(ll a,ll b)
{
ll res=1;
while(b)
{
if(b&1)
res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
signed main()
{
int a,b;
cin>>a>>b;
if(a==0)
{
cout<<0<<endl;
return 0;
}
for(int i=2;i*i<=a;i++)
{
if(a%i==0)
{
int cnt=0;
while(a%i==0)
{
a/=i;
cnt++;
}
v.pb(mp(i,cnt*b));
}
}
if(a!=1)
v.pb(mp(a,b));
int res=1;
for(auto i:v)
{
int t=(qpow(i.fi,i.se+1)+mod-1)%mod*qpow(i.fi-1,mod-2)%mod;
if(i.fi%mod==1)
res=res*(i.se+1)%mod;
else
res=res*t%mod;
}
cout<<res<<endl;
}
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)