「NOIP模拟赛」calc
题目说明
给三个正整数n，m和p，求(n^1+…n^m) mod p。
输入格式
一行，三个整数n，m和p。
输出格式
输出答案。
样例
Sample Input
2 2 5
Sample Output
1
数据范围
n,p<=10^8 m<=10^17
相关信息
文件名: calc.pas/c/cpp
输入文件: calc.in
输出文件: calc.out
时限: 1s
空间限制: 64MB
题解
暴力直接快速幂
正解应该是矩阵乘法
然后我作死试图用数论。。。逆元没学好
根据等比数列求和公式得到（省略）/（n-1） mod p
发现n-1和p可能不互质，然后（省略）/（n-1） 和 p 都乘上gcd，最后答案除以gcd
这样就能用乘法逆元算了
假设数据这样乱搞不会爆longlong
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #define ll long long using namespace std; ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll ans; ll n,m,p,t=1; ll gcd(ll a,ll b) { return b==0?a:gcd(b,a%b); } void exgcd(ll a,ll b,ll &x,ll &y) { if(b==0){x=1;y=0;return;} exgcd(b,a%b,x,y); ll t=x;x=y;y=t-a/b*y; } ll ine(ll T)//aT+py=1 { ll x,y; exgcd(T,p,x,y); while(x<0)x+=p; return x; } ll qpow(ll x,ll y) { ll ans=1; x%=p; for(ll i=y;i;i>>=1,x=x*x%p) if(i&1)ans=ans*x%p; return ans; } void cal() { ll s2=n-1; t=gcd(s2,p); s2/=t;p*=t; ll s1=(qpow(n,m+1)-n%p+p); ans=s1*ine(s2)%p; } int main() { // freopen("calc.in","r",stdin); // freopen("calc.out","w",stdout); n=read();m=read();p=read();// n^(m+1)-n if(m<=200000) { for(ll i=1;i<=m;i++) ans=(ans+qpow(n,i))%p; } else cal(); cout<<ans/t; return 0; } |
Subscribe
计数器 9786427
OI 课件=>
OI 课件=>