louisfghbvc的部落格

題目大意:  算A0~An加總，An = An-1*An-1%m

思路:  N很大，所以從m下手，因為%m，所以數字的範圍一定會在這裏面，而且會有環。所以關鍵在找環。

我這邊用Floyd Cycle。龜兔賽跑演算法，假設相遇點為a，則烏龜前進了 F+a。兔子前進了 F+nC + a。F為進入環之前的距離

(2倍烏龜=1倍兔子)所以 2(F+a) = F+nC+a => F + a = nC，所以說如何找環的進入點，當烏龜在0的時候，前進了F ，兔子在剛剛的相遇點前進F 所以兔子 F+nC + a + F

不就等於 nC + nC + F, 烏龜在F。 假設n是0，那不就得到了進入點?

所以有了進入點之後，就可以算環有多長。最後就看用了幾次環。

這場解4題(1235)，第6題，等我能夠一場解出5題在看，因為看起來頗噁心。

代碼:  

#include <bits/stdc++.h>
 
#define Fast cin.tie(0), ios::sync_with_stdio(0)
#define All(x) x.begin(), x.end()
#define louisfghbvc int t; cin >> t; while(t--)
#define sz(x) (int)(x).size()
using namespace std;
typedef long long LL;
typedef pair<LL, LL> ii;
typedef vector<LL> vi;
 
template<typename T> istream& operator>>(istream &is, vector<T> &v) { for(auto &it : v) is >> it; return is; }
template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { os << '{'; string sep = ""; for(const auto &x : v) os << sep << x, sep = ", "; return os << '}'; }
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
 
void dbg_out() { cerr << "\n"; }
template<typename Head, typename... Tail> void dbg_out(Head H, Tail... T) { cerr << ' ' << H; dbg_out(T...); }
 
const int N = 2e5+5;
 
void solve(){
    LL n, x, m;
    cin >> n >> x >> m;
    LL res = 0;
 
    LL slow = x, fast = x;
    do{
        slow = slow*slow%m;
        fast = fast*fast%m;
        fast = fast*fast%m;
    }while(slow != fast);
 
    fast = x;
    int L = 0;
    while(slow != fast){
        res += fast;
        L++;
        if(L == n){
            cout << res << "\n";
            return;
        }
        slow = slow*slow%m;
        fast = fast*fast%m;
    }
    n -= L;
 
    vi cyc;
    do{
        cyc.push_back(slow);
        slow = slow*slow%m;
    }while(slow != fast);
 
    LL cyclen = sz(cyc);
    for(int i = 0; i < cyclen; ++i){
        res += (n/cyclen)*cyc[i];
    }
    n %= cyclen;
    for(int i = 0; i < n; ++i){
        res += cyc[i];
    }
    cout << res << "\n";
}
 
int main()
{
    Fast;
    //louisfghbvc{
        solve();
    //}
    return 0;
}