A simple Blog for wyx I've been down the bottle hoping.
3884: 上帝与集合的正确用法 数论 欧拉定理 欧拉函数
发表于: | 分类: Oi | 评论:0 | 阅读:38

大爷这题其实是骗人的……

如果你做过古代猪文你会发现这题,逗你的

$$f(p) = a^x(mod \ p) = a^{x\ mod \phi(p)+\phi(p)}(mod \ p) = a^{f(\phi(p))+\phi(p)}(mod\ p)$$

然后你每次递归下去就行了……显然每次至少缩小一半……

边界的话$f(1)=0$

#include <map>
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
map <int,int> mp;

inline LL pow(LL a,LL b,LL mod) {
    LL res = 1;
    for(;b;b>>=1,a=a*a%mod)
        if(b&1)
            res  = res * a % mod;
    return res;
}

inline LL calc(LL n) {
    LL ans = n;
    register int i;
    for(i=2;i*i<=n;++i) {
        if(n%i==0) {
            while(n%i==0) n/=i;
            ans /= i; ans *= (i-1);
        }
    }
    if(n>1) ans /= n, ans *= (n-1);
    return ans;
}

LL get(LL n) {
    if(mp.count(n)) return mp[n];
    LL tt = calc(n);
    return (mp[n] = pow(2,get(tt)+tt,n));
}

int main() {
    int T; cin >> T; mp[1] = 0;
    while(T -- ){
        LL n; scanf("%lld",&n);
        printf("%lld\n",get(n));
    }
}

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP