Lijinrui299792458

不做沉底的木做举重若轻的船。

数论（2）

发表于 更新于

欧拉定理的推广

欧拉定理要求 $\gcd(a,m)=1$，因此在 $a,m$ 不互质时无法直接使用。对于 $a,m$，若 $gcd(m,a)\ne 1$ 且 $x>\varphi(m)$，有
$$
a^x\equiv a^{x\mod\varphi(m)+\varphi(m)}\mod m
$$
证明：
$$
m=\prod_{i=1}^{n}p_i^{q_i},a=s\prod_{i=1}^{n}p_i^{k_i},\gcd(s,m)=1
$$

$$
即证:t\ge1,a^{t\varphi(m)}\equiv s^{t\varphi(m)}\prod_{i=1}^{n}p_i^{t\varphi(m)k_i}\equiv a^{\varphi(m)}\mod m
$$

$$
对于 k_i=0,p_i^{t\varphi(m)k_i}\equiv1\mod m
$$

$$
\varphi(m)\ge\varphi(p_i^{q_i})=p_i^{q_i-1}(p_i-1)\ge2^{q_i-1}\ge q_i
$$

$$
p_i^{b\varphi(m)}\equiv1 \mod \left(\frac{m}{p_i^{q_i}}\right),p_i^{b\varphi(m)+q_i}\equiv p_i^{q_i}\mod m
$$

$$
p_i^{(b+1)\varphi(m)}\equiv p_i^{\varphi(m)}\mod m
$$

显然，原命题成立。

例

P4139 上帝与集合的正确用法

思路

$$
2^{2^{2\cdots}}\equiv 2^{\left(2^{2\cdots}\mod\varphi(p)+\varphi(p)\right)}\equiv2^{\left(2^{\left(2^{2\cdots}\mod\varphi(\varphi(p))+\varphi(\varphi(p))\right)}\mod\varphi(p)+\varphi(p)\right)}\mod p
$$

当 $\varphi(\varphi(\cdots\varphi(p)))=1$ 时，在往上的 $2$ 就对答案没有影响了，而容易看出，这些 $2$ 最多有 $\log$ 层。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include<bits/stdc++.h>

#define ll long long

using namespace std;

ll t,p;
ll pri[700000],phi[10000001],cnt;
bool ntpr[10000001];

inline void init()
{
    phi[1]=1;
    for(int i=2;i<=10000000;i++)
    {
		if(!ntpr[i])
        {
            pri[++cnt]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=cnt&&pri[j]*i<=10000000;j++)
        {
            ntpr[i*pri[j]]=1;
			if(!(i%pri[j]))
            {
                phi[i*pri[j]]=phi[i]*pri[j];
                break;
            }
            phi[i*pri[j]]=phi[i]*phi[pri[j]];
        }
    }
}

inline ll quik_pow(ll a,ll b,ll mod)
{
    ll ret=1,_=a;
    while(b)
    {
        if(b&1)ret*=_,ret%=mod;
        _=_*_,_%=mod;
        b>>=1;
    }
    return ret;
}

inline ll solv(ll _)
{
    if(_==1)return 1LL;
    return quik_pow(2LL,solv(phi[_])+phi[_],_);
}

int main()
{
    init();
    cin>>t;
    while(t)
    {
        t--;
        cin>>p;
        cout<<solv(p)<<endl;
    }
    return 0;
}