BZOJ 3884 하느님 과 집합의 정확 한 용법

제목:http://www.lydsy.com/JudgeOnline/problem.php?id=3884
제목: 222... modp 의 값, 여러 그룹 문의.p≤107 .
문제 풀이: 오로라 의 정 리 를 고려 하여 (a, p) = 1 시, aϕ(p)≡1(modp) . 이 를 통 해 x ≥ 라 는 결론 을 쉽게 얻 을 수 있다.ϕ있다
ax≡axmodϕ(p)+ϕ(p)(modp)
증명 과정 과 큰 걸음 작은 걸음 알고리즘 을 확장 하 는 소 인자 과정 이 유사 하 므 로 번 거 로 움 을 느끼 지 않 고 참고 할 수 있 습 니 다.AekdyCoin 의 글 [A ^ x = A ^ (x% Phi (C) + Phi (C))) (mod C) 에 대한 약간의 증명] [지수 순환 절]
이 문제 로 돌아 가 f (p) = 222... modp 라면 f (1) = 0.또 무한 식 이기 때문에 222... 의 지 수 는 원래 초과 합 니 다.ϕ(p) 의, 그래서 우 리 는 고 칠 수 있다.
f(p)=2(22...modϕ(p))+ϕ(p)modp=2f(ϕ(p))+ϕ(p)modp
그래서 얻 었 다.
f (p) 의 전달 식.
이렇게 계산 하 는 것 은 O (p) 인 것 같 지만, 우 리 는 맞 출 수 있다.ϕ(ϕ(...ϕ(p))) 분석: p 가 짝수 라면ϕ(p)≤p2 ; p 가 홀수 라면 p 에 홀수 인자 q 가 존재 합 니 다.ϕ(p) 짝수 인자 (q - 1) 가 존재 하여 짝수 로 바 뀌 는 경우.이로부터 알 수 있 듯 이ϕ(ϕ(...ϕ(p))) 의 계산 은 O (logp) 차 의 교 체 를 거 쳐 1 에 이 르 렀 기 때문에 f (p) 의 계산 은 O (p √ logp) 의 것 이다.
출제 자가 내 놓 은 해법 도 O (p √ logp) 이 니 관심 있 는 것 은 가 봐 도 무방 하 다.
코드:

#include <map> 
#include <cstdio>
using namespace std;
map<int, int> f;
int pow(int x, int k, int p)
{
    int ret = 1;
    while(k)
    {
        if(k & 1)
            ret = (long long)ret * x % p;
        x = (long long)x * x % p;
        k >>= 1;
    }
    return ret;
}
int phi(int x)
{
    int ret = x;
    for(int i = 2; i * i <= x; ++i)
        if(x % i == 0)
        {
            ret -= ret / i;
            while(x % i == 0)
                x /= i;
        }
    if(x > 1)
        ret -= ret / x;
    return ret;
}
int F(int x)
{
    if(f.count(x))
        return f[x];
    int p = phi(x);
    return f[x] = pow(2, F(p) + p, x);
}
int main()
{
    int t, n;
    scanf("%d", &t);
    f[1] = 0;
    while(t--)
    {
        scanf("%d", &n);
        printf("%d
", F(n));
    }
    return 0;
}