cfgym101252D

201707 （ACM）思维

题意

题解

• 一开始感觉用map存就行了，然后MLE了。
• 后来各种优化空间复杂度。
• 但是其实这道题时间给了10s。
  
  • 如果循环节存在，那么第2e7个肯定和前面的某一个相等。由此我们找出循环节。
  • 然后双指针for一遍即可。

代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define rep(i, a, b) for(int i=(a); i<(b); i++)
#define sz(a) (int)a.size()
//---------------
const int N=2e7+1;
ll a,b,c;
void upd(ll &x) {
    x=(a*x+x%b)%c;
}
int main() {
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
    while(~scanf("%lld%lld%lld",&a,&b,&c)) {
        ll xn=1;
        rep(i,1,N) upd(xn);
        ll now=1;
        int len=-1;
        rep(i,1,N-1) {
            upd(now);
            if(now==xn) {
                len=i;
            }
        }
        if(len==-1) {
            puts("-1");
            continue;
        }
        len=N-1-len;
        ll p1=1,p2=1;
        rep(i,1,len+1) upd(p2);
        int ans=-1;
        rep(i,len,N+1) {
            if(p1==p2) {
                ans=i;
                break;
            }
            upd(p1);upd(p2);
        }
        printf("%d\n",ans);
    }
    return 0;
}