生活随笔
收集整理的這篇文章主要介紹了
SDUT -2605 A^X mod P(数论+思维)
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
題目鏈接：點擊查看
題目大意：給出一個遞推式得到 f[ i ] ，現在需要求?
題目分析：最簡單的做法就是 nlogn ，帶個快速冪，顯然這個題目是不可能這么簡單的
考慮將冪次化簡，設 f[ i ] = x ，又因為 m?∈ [ 0 , 1e9 ] ，所以 x ∈ [ 0 , 1e9 ] ，我們可以以 1e5 為分界點分塊，得到，顯然我們可以 O( 1e5 ) 分別預處理出??和??，然后就有? 了，剩下的就可以 O( n ) 計算得出答案了
代碼：
?
#include<iostream>
#include<cstdio>
#include<string>
#include<ctime>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<stack>
#include<climits>
#include<queue>
#include<map>
#include<set>
#include<sstream>
#include<cassert>
#include<bitset>
using namespace std;typedef long long LL;typedef unsigned long long ull;const int inf=0x3f3f3f3f;const int N=2e5+100;const int M=1e5;LL n,A,K,a,b,m,P,sum1[M+100],sum2[M+100];//sum1[i]=A^i,sum2[i]=A^(M*i)void init()
{sum1[0]=sum2[0]=1;for(int i=1;i<=M;i++)sum1[i]=sum1[i-1]*A%P;for(int i=1;i<=M;i++)sum2[i]=sum2[i-1]*sum1[M]%P;
}int main()
{
#ifndef ONLINE_JUDGE
// freopen("data.in.txt","r",stdin);
// freopen("data.out.txt","w",stdout);
#endif
// ios::sync_with_stdio(false);int w;cin>>w;int kase=0;while(w--){scanf("%lld%lld%lld%lld%lld%lld%lld",&n,&A,&K,&a,&b,&m,&P);init();LL ans=0;for(int i=1;i<=n;i++){ans=(ans+sum1[K%M]*sum2[K/M])%P;K=(a*K+b)%m;}printf("Case #%d: %lld\n",++kase,ans);}return 0;
}
?
超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生
總結
以上是生活随笔為你收集整理的SDUT -2605 A^X mod P(数论+思维)的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
