B. Moodular Arithmetic

Division Modular, Number Theory


출처: Codeforces B. Moodular Arithmetic

SOL)
k = 0일 때 무조건 f(0) = 0이어야 하고 나머지는 p개 중 고르면 된다.
즉, p^(p-1)
k = 1일 때 모든 값을 은 p개를 고를 수 있다.
즉, p^p
k > 1일 때 연관 관계를 찾아야한다.
예를 들어서
p = 5, k = 2일 때
{f(0), 2*f(0)}, {f(2), 2*f(1)}, {f(4), 2*f(2)}, {f(1), 2*f(3)}, {f(3), 2*f(4)}
위와 같이 함수 패어가 나오는데 f(0) = 0이어야 하고
나머지는 연관관계를 봐야한다. 그래서 이문제가 dfs태그도
붙은거 같다. 위 예는 f(2)가 결정되면 나머지 모든값들이 결정된다.
하지만
p = 5, k = 4일 때
{f(0), 4*f(0)}, {f(4), 4*f(1)}, {f(3), 4*f(2)}, {f(2), 4*f(3)}, {f(1), 4*f(4)}
위와 같이 함수 쌍이 나오는데 {f(1), f(4)} 와 {f(2), f(3)} 두 부류로
나눠짐을 확인할 수 있다. 즉 각각이 p개를 선택할 수 있어서
답은 5^2이다.

p = 5, k = 2 일때
같은 부류를 조사해야하는데 (k*x) mod = r 이 때 r은 이전의 x로
예를 들어 처음 스타트 값으로 srt = k, r = 1로 시작을 한다
그럼이제 우리는 3을 찾아내야 한다. 이 때 division modular를 이용한다.

주의!. power(k, p-2)를 할때 주어진 mod 10^9+1을 하면 안된다.



[-] Collapse

#include<stdio.h>
typedef long long ll;
const ll mod = 1000000007;
ll power(ll a, ll b){
    ll val = 1;
    while (b){
        if (b & 1) b--, val *= a;
        a *= a;
        b >>= 1;
        a %= mod;
        val %= mod;
    }
    return val;
}

ll p, k;

int main(){
    //freopen("input.txt", "r", stdin);
    scanf("%lld %lld", &p, &k);

    if (k == 0) printf("%lld", power(p, p - 1));
    else if (k == 1) printf("%lld", power(p, p));
    else{
        ll cnt = 1;
        ll srt = k * 1;
        ll r = 1;
        ll inverse = 1;
        for (int i = 0; i < p - 2; i++){
            inverse *= k;
            inverse %= p;
        }
        while (srt != r){
            cnt++;
            r = (r * inverse) % p;
        }
        printf("%lld", power(p, (p - 1) / cnt));
    }
    return 0;
}