一.基本理论

1.基本概念：

给定一个正整数p，任意一个整数n，一定存在等式 $n=kp+r$n=kp+r
　　
其中 $k、r$k、r是整数，且 0≤r<p，称呼 $k$k为 $n$n除以 $p$p的商， $r$r为 $n$n除以p的余数。

对于正整数p和整数 $a,b$a,b，定义如下运算：

取模运算： $a\%p（或amodp）$a%p（或amodp），表示a除以p的余数。

模p加法： $(a+b)\%p$(a+b)%p ，其结果是 $a+b$a+b算术和除以p的余数，也就是说， $(a+b)=kp+r，$(a+b)=kp+r，则 $(a+b)\%p=r。$(a+b)%p=r。

模p减法： $(a-b)\%p$(a−b)%p，其结果是 $a-b$a−b算术差除以p的余数。

模p乘法： $(a\ast b)\%p$(a∗b)%p，其结果是 $a\ast b$a∗b算术乘法除以p的余数。

2.说明：

1. 同余式：正整数 $a，b$a，b 分别对 $p$p 取模，它们的余数相同，记做 $a\equiv b\%p$a≡b%p或者 $a\equiv b\left(modp\right)。$a≡b(modp)。

2. $n\%p$n%p得到结果的正负由被除数n决定,与p无关。例如： $7\%4=3$7%4=3， $-7\%4=-3，7\%-4=3，-7\%-4=-3$−7%4=−3，7%−4=3，−7%−4=−3。

3.基本性质

（1）若 $p\mid (a-b)，$p∣(a−b)，则 $a\equiv b\left(\%p\right)$a≡b(%p)。例如 $11\equiv 4\left(\%7\right)，$11≡4(%7)， $18\equiv 4\left(\%7\right)$18≡4(%7)

（2） $\left(a\%p\right)=\left(b\%p\right)$(a%p)=(b%p)意味 $a\equiv b\left(\%p\right)$a≡b(%p)

（3）对称性： $a\equiv b\left(\%p\right)$a≡b(%p)等价于 $b\equiv a\left(\%p\right)$b≡a(%p)

（4）传递性：若 $a\equiv b\left(\%p\right)$a≡b(%p)且 $b\equiv c\left(\%p\right)$b≡c(%p)，则 $a\equiv c\left(\%p\right)$a≡c(%p)

运算规则

模运算与基本四则运算有些相似，但是除法例外。其规则如下：

$(a+b)\%p=(a\%p+b\%p)\%p$(a+b)%p=(a%p+b%p)%p （1）

$(a-b)\%p=(a\%p-b\%p)\%p$(a−b)%p=(a%p−b%p)%p （2）

$(a\ast b)\%p=(a\%p\ast b\%p)\%p$(a∗b)%p=(a%p∗b%p)%p （3）

$\left(a^b\right)\%p=\left(\right(a\%p{)}^b)\%p$(ab)%p=((a%p)b)%p （4）

结合率： $\left(\right(a+b)\%p+c)\%p=(a+(b+c\left)\%p\right)\%p$((a+b)%p+c)%p=(a+(b+c)%p)%p（5）

$\left(\right(a\ast b)\%p\ast c)\%p=(a\ast (b\ast c\left)\%p\right)\%p$((a∗b)%p∗c)%p=(a∗(b∗c)%p)%p （6）

交换率： $(a+b)\%p=(b+a)\%p$(a+b)%p=(b+a)%p （7）

$(a\ast b)\%p=(b\ast a)\%p$(a∗b)%p=(b∗a)%p （8）

分配率： $\left(\right(a+b)\%p\ast c)\%p=\left(\right(a\ast c)\%p+(b\ast c\left)\%p\right)\%p$((a+b)%p∗c)%p=((a∗c)%p+(b∗c)%p)%p （9）

**重要定理：**若 $a\equiv b\left(\%p\right)，$a≡b(%p)，则对于任意的 $c$c，都有 $(a+c)\equiv (b+c)\left(\%p\right)$(a+c)≡(b+c)(%p)；（10）

若 $a\equiv b\left(\%p\right)$a≡b(%p)，则对于任意的 $c$c，都有 $(a\ast c)\equiv (b\ast c)\left(\%p\right)$(a∗c)≡(b∗c)(%p)；（11）

若 $a\equiv b\left(\%p\right)$a≡b(%p)， $c\equiv d\left(\%p\right)$c≡d(%p)，则 $(a+c)\equiv (b+d)\left(\%p\right)$(a+c)≡(b+d)(%p)， $(a-c)\equiv (b-d)($(a−c)≡(b−d)(，

$(a\ast c)\equiv (b\ast d)\left(\%p\right)$(a∗c)≡(b∗d)(%p)， $\left(a/c\right)\equiv \left(b/d\right)\left(\%p\right)$(a/c)≡(b/d)(%p)； （12）

若 $a\equiv b\left(\%p\right)$a≡b(%p)，则对于任意的 $c$c，都有 $ac\equiv bc\left(\%p\right)$ac≡bc(%p)； （13）

二.基本应用

1.判别奇偶数　　2.判别素数3. 最大公约数　　4．模幂运算

1.快速幂运算

UVA10006 Carmichael Numbers

一个数是 $CarmichaelNumbers$CarmichaelNumbers
得满足它不是质数并且对于每一个 i(1<i<n)都满足 $i^n\equiv imod\hspace{0.17em}\hspace{0.17em}n$in≡imodn
我们如果暴力求解 $i^n$in
时间复杂度是 $O\left(n\right)$O(n)妥妥的 $TLE$TLE
我们引进一个高效求 $x^y$xy 的东西:
快速幂
什么是快速幂呢，就是把 $x^y$xy
变为
(1) $ymod\hspace{0.17em}\hspace{0.17em}2=0:x^y=(x^2{)}^{y/2}$ymod2=0:xy=(x2)y/2(

(2) $ymod\hspace{0.17em}\hspace{0.17em}2=1:x^y=x\ast x^{y-1}$ymod2=1:xy=x∗xy−1 ，此时y为偶数

因为每次 $y$y 都会除以2
所以快速幂的时间复杂度就为 $O\left(lo{g}_{2}y\right)$O(log2​y)
那么此题的时间复杂度就为 $O(T\ast (\sqrt{n}+n\ast lo{g}_{2}n\left)\right)$O(T∗(n ​+n∗log2​n))

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ifstream in("input.txt");
ofstream out("output.txt");
#define debug(x) cout<<"# "<<x<<endl
const ll N=100005;
const ll base=137;
const ll mod=2147483647;
const ll INF=1<<30;
ll n,m,x;
ll mod_pos(ll x,ll n,ll mod)
{
    ll res=1;
    while(n)
    {
        if(n&1)res=res*x%mod;
        x=x*x%mod;
        n>>=1;
    }
    return res;
}
int main()
{
    while(~scanf("%lld",&n)&&n!=0)
    {
        bool flag=true;
        for(int i=2;i*i<=n;++i){
            if(n%i==0)
                flag=false;
        }
        if(flag){
            printf("%lld is normal.\n",n);
            continue;
        }
        flag=true;
        for(int i=2;i<n;++i)
        {
            if(mod_pos(i,n,n)!=i){
                flag=false;
                printf("%lld is normal.\n",n);
                break;
            }
        }
        if(flag)printf("The number %lld is a Carmichael number.\n",n);
    }
    return 0;
}