The solution of「CF603B Moodular Arithmetic」

· · 题解

\textup{CF603B Moodular Arithmetic}

\textup{Luogu} | \textup{Codeforces} | \textup{Cnblogs} | 计数。

先说好，发现自己讲的很啰嗦，且思路借鉴楼上的题解。

\textup{Description}

给定 p,k，求有多少种方案可以构造出序列 f_i 使得 \forall i, f_i < p 且 f_{k \cdot x \bmod p} = k \cdot f_{x \bmod p}。

\textup{Solution}

赛时想的太偏了呀，没有战胜呜呜呜。

我们发现，一个 f_i 会指向另一个，感觉到会连出一个环。

我们先考虑普通情况，可以这么推，对于 f_i 会连出的点有：

\large f_i \to f_{k \cdot i} \to f_{k ^ 2 \cdot i} \to \cdots f_{k^{y} \cdot i}

那么有 k ^ {y} \cdot i \equiv i \ (\bmod p)，i \not\equiv 0 时，即 k ^ {y} \equiv 1 \ (\bmod p)。

我们再代入到题目给出的式子，发现：

\large f_i = f_{k ^ y \cdot i} = k ^ y \cdot f_i

这样就证明了一定可以化作一个环，且环首 f_i 我们知道后整个环就定下来了。

此时所有环长相等，都是是 y，即满足 k ^ {y} \equiv 1 \ (\bmod p) 的最小正整数。

因为是第一次遇到，且 y,p 互质，这个是费马小定理的一个推论。

由于 f_i 有 p 种选法，故每个环有 p 种方案。

总共有 \frac{p - 1}{y} 个环，于是贡献为 p^{\large \frac{p - 1}{y}}。

接着思考一些特殊情况，比如 k = 0 / 1 的情况，因为 0 的时候就不可能形成环了，而 1 的时候就变成一堆自环了，所以需要特判断。这也是赛时给我们的部分分。

最后，y 直接暴力去找就可以了，费马小定理保证了存在性，且最多跑 p - 1，非常的好。

\textup{Code}

\textup{Rec.}

#include<bits/stdc++.h>
#define int long long
using namespace std;
const long long inf = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;
int P, K, ans;
int qpow( int a, int b ){
    int ans = 1;
    while( b ){
        if( b & 1 ) ans = ( ans * a ) % MOD;
        a = ( a * a ) % MOD;
        b >>= 1;
    }
    return ans;
}

void slove(){
    cin >> P >> K;
    if( K == 0 ){
        cout << qpow( P, P - 1 );
        return;
    }
    if( K == 1 ){
        cout << qpow( P, P );
        return;
    }
    int cnt = 1, now = K;
    while( now != 1 ){
        now = ( now * K ) % P;
        cnt ++;
    }
    cout << qpow( P, ( P - 1 ) / cnt );
}
signed main(){
    // freopen( "hard.in", "r", stdin );
    // freopen( "hard.out", "w", stdout );
    ios::sync_with_stdio( false );
    cin.tie( 0 );
    cout.tie( 0 );
    int T = 1;
    // cin >> T;
    while( T -- )
        slove();
    return 0;
}

\textup{Last}

审核管理员辛苦了，如果您有所疑惑或我有所错漏，请您在评论区指出或找我，我会一定解答并且修改本题解。

如果您觉得本文写的还不错，那可以留个赞吗？

谢谢你看到这里~