同余、欧拉函数和逆元

coresidual and Euler function and Inverse element

1.同余(coresidual)

1.1 定义和两个常见性质

特别的

2.线性同余方程

两者等价
一开始我们由,然后对前面的系数辗转相除即可

$①$
$②$
$① ②$ $③$

$② ③$ $④$
$③ ④$ $⑤$
$④ ⑤$

3.简化剩余系

所有的满足构成了一个模的简化剩余系

欧拉函数
定义：小于m的正整数中与m互质的数的数目
记这样n的个数为
特别的：如果是素数,则

中有多少互质的，既不是的倍数，也不是的倍数,也不是的倍数

$==>30*(1-1/2)(1-1/3)(1-1/5)==>30*(1-1/2-1/3-1/5+1/6+1/10+1/15-1/30)$

$以内$

4.欧拉定理

如果,那么
证明：当取遍模的化简剩余系时,也取遍模的简化剩余系
集合小于等于的且与互质的正整数集合
――――与互质，模后各不相同

集合为{ %,%…% }

因为与互质,所以%也与互质，即中各元素均与互质

即

5.推论(扩展欧拉定理)

我们知道，对于互质的情况：

当时，

可以转化为 ,因为每

接下来我们看不互质的情况：

考虑在不互质的情况下会不会有相似的结论呢？

背景:我们举个例子看看

![image-20230626120103489](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230626120103489.png)

先说扩欧的结论：

当时

感性的来说:

![image-20230626120117272](C:\Users\Zhou Yanan\AppData\Roaming\Typora\typora-user-images\image-20230626120117272.png)

扩欧板子

例题1:BZOJ 3884, 上帝与集合的正确用法

给定一个数字，求

的值。

理解一下题意：

当无限大的时候我们知道是一个定值

因为这个东西它不一定是互质的，我们只需要把它的指数求出来，比如说求出来是，那我们只需要求就行了，然后我们发现它的幂次又是相同的子问题。也就是想要知道指数是多少，就要知道这个指数的指数是多少

先说几个结论:

1.除了以外，其他数的都是偶数

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll p;
ll ksm(ll a,ll b,ll m)
{
	ll ans = 1,base = a;
	while(b>0)
	{
		if(b&1)
		{
			ans *= base;
			ans %= m;
		}
		base *= base;
		base%=m;
		b>>=1;
	}
	return ans;
}


ll calc(int p)
{
	if(p==1)return 0;
	int phip = p,q = p;
	for(int i = 2;i*i<=q;i++)
	{
		/*
		m以内p1^e1*p2^e2...pk^ek
		==>m(1-1/p1)(1-1/p2)...(1-1/pk)
		*/
		if(q%i==0)
		{
			phip = phip/i*(i-1);
			while(q%i==0)q/=i;
		}
	}
	if(q!=1)phip = phip/q*(q-1);
	return ksm(2,calc(phip)+phip,p);
}

void solve()
{
	cin>>p;
	cout<<calc(p)<<endl;
}

int main()
{
	int t;
	cin>>t;
	for(int i = 1;i<=t;i++)
	{
		solve();
	}
	return 0;
}

例题2：CF D. Power Tower

题意：

给定一个数列和模数p,每次询问一个区间[l,r],求的值

如果你看不懂上面的式子，它其实是这样运算的:

题解：

想要知道是多少，就要知道它的指数是多少，像要知道它的指数是多少，就要知道它指数的指数是多少。

我们知道这个迭代轮之后会变成,也就是说我们只需要关注前项，因为后面的是不会影响答案的。

对比上一个例题，上一个例题因为一定是的，那我们就可以无脑带公式：指数就行了。

但这题，指数是有可能小于的，那我们每次,如果这个东西我们就返回它原来的值，否则返回模之后加上的值.

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 101000;
int n,q,m,p[100],a[N],t;
ll ksm(ll a,ll b,ll m)
{
	ll ans = 1,base = a;
	while(b>0)
	{
		if(b&1)
		{
			ans *= base;
			ans %= m;
		}
		base *= base;
		base%=m;
		b>>=1;
	}
	return ans;
}

ll phi(int p)
{
	int phip = p,q = p;
	for(int i = 2;i*i<=q;i++)
	{
		if(q%i==0)
		{
			phip = phip/i*(i-1);
			while(q%i==0)q/=i;
		}
	}
	if(q!=1)phip = phip/q*(q-1);
	return phip;
}

int solve(int l,int r,int x)
{
	int q = p[x];
	if(l==r)return a[l]<q?a[l]:(a[l]%q+q);
	if(q==1)return 1;
	int d = solve(l+1,r,x+1);
	int ans = ksm(a[l],d,p[x]);
	//看a[l]^d < q?
	bool isles = true;
	if(a[l]!=1)
	{
		if(d>=30)//2^30次方肯定>q了
			isles =  false;
		else if(pow(a[l],d)>=1e9)isles = false;
		else//pow算出的可能有误差
		{
			int  val = ksm(a[l],d,1e9+7);
			if(val>=q)isles = false;
		}
	}
	if(!isles)ans += q;
	return ans;
}



int main()
{
	cin>>n>>m;
	p[t++] = m;
	while(p[t-1]!=1)
	{
		p[t] = phi(p[t-1]);
		t+= 1;
	}
	for(int i = 1;i<=n;i++)
	{
		cin>>a[i];
	}
	cin>>q;
	while(q--)
	{
		int l,r;
		cin>>l>>r;
		//0表示mod p[0]
		cout<<solve(l,r,0)%m<<endl;
	}
	return 0;
}

欧拉函数筛法

//筛法：
int phi[3000001];
void phi_table(){
    //memset(phi,0,sizeof(phi));
    phi[1]=1;
    for(int i=2;i<=3000000;i++){
        if(!phi[i])
        for(int j=i;j<=3000000;j+=i){
            if(!phi[j])
                phi[j]=j;
            phi[j]=phi[j]/i*(i-1);
        }
    }
}

//单个phi
ll phi(ll n) {
    ll ans = n;
    for(int i = 2; i*i <= n; i++) {
        if(n%i==0) {
            ans-=ans/i;
            while(n%i==0)
                n/=i;
        }
    }
    if(n > 1)   ans-=ans/n;
    return ans;
}

//线性筛phi
//记得在main里面先调用sieve
const int N=(1<<16)+5;
int n,tot,p[N];
bool flg[N];

void sieve(int n) {
    for(int i=2;i<=n;++i) {
        if(!flg[i]) p[++tot]=i;
        for(int j=1;j<=tot&&i*p[j]<=n;++j) {
            flg[i*p[j]]=1;
            if(i%p[j]==0) break;
        }
    }
}
long long phi(long long x) {
    long long ans=x;
    for(int i=1;i<=tot&&1LL*p[i]*p[i]<=x;++i) {
        if(x%p[i]) continue;
        ans=ans/p[i]*(p[i]-1);
        while(x%p[i]==0) x/=p[i];
    }
    if(x>1) ans=ans/x*(x-1);
    return ans;
}

//同时筛出质数表和欧拉函数表：
//O(nloglogn)
const int MAXN=1000000;
bool check[MAXN+10];
int phi[MAXN+10];
int prime[MAXN+10];
int tot;
void phi_and_prime_table(int N){
    memset(check,0,sizeof(check));
    phi[1]=1;
    tot=0;
    for(int i=2;i<=N;i++){
        if(!check[i]){
            prime[tot++]=i;
            phi[i]=i-1;
        }
        for(int j=0;j<tot;j++){
            if(i*prime[j]>N)
                break;
            check[i*prime[j]]=1;
            if(i%prime[j]==0){
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else{
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            }
        }
    }
}

❗欧拉函数性质

当时，是偶数。

证明(重要！)：由于相像减损术，

若互质，则有。

所以对于每一个互质的数，都有对应一个与之互质，所以是偶数。

任意，中所有于互质的数的和为。

证明：因为，所以于不互质的数一定成对出现，平均值为，所以互质的数的平均值也为.

3. (重要！)

推论：

LCMSUM - LCM Sum
若 $，$ 不互质，则

证明：

$且$

6.费马小定理(可以看作欧拉定理的特殊版本)

特别的当m是质数,φ(p) = p-1

它可以用来判断大质数也就式Miller-Rabin质数判定
它可以用来进行费马小定理降幂也就是
求解逆元

7.逆元

1>定义

是的逆元
除法的取模中运用

2>求逆元

法一：

由于
那么
如果m为素数,那么答案为
即：(费马小定理)
用ksm求就ok

否则需将m(合数)分解,或解线性同余方程

法二：exgcd求逆元

,即丢番图方程，先用求的一个特解,通解是,然后通过取模操作计算最小整数解，因为可以保证结果为正。

typedef long long ll;
ll exgcd(ll a,ll b,ll &x,ll &y)
{
	if(b==0)
    {
        x = 1,y = 0;
        return a;
    }
    int d = exgcd(b,a%b,y,x);
    y -= (a/b)*x;
    return d;
}
ll mod_inv(ll a,ll b)
{
    ll x,y;
    exgcd(a,b,x,y);
    return (x%m+m)%m;
}

特别的：

逆元1 a.求1~n的逆元

$-\dfrac{p}{i}i ≡ (p \bmod i)-\dfrac{p}{i} ≡ i^{-1}(p \bmod i)-\dfrac{p}{i}(p \bmod i)^{-1} ≡ i^{-1}$

可以看出的逆元可以有的逆元逆推得到

需要将的逆元初始化为，因为%

注意负数取模，对取模需要先将负数变为正数在进行取模操作

//求1~n的逆元
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 1e7+10;
ll inv[N],n,p;
int main()
{
	cin>>p>>n;
	inv[1] = 1;
	ll ans = 1;
	for(int i = 2;i<=n;i++)
	{
		inv[i] = (p-p/i)*inv[p%i]%p;
		ans = ans^inv[i];
	}
	cout<<ans<<endl;
	return 0;
}

逆元2

/*
a1,a2,...,an
s1 = a1,s2 = a1*a2,...,sn = a1*a2...*an
si = si-1*ai
ti = si^-1 = a1^-1*a2^-1...ai^-1
sn—求一次逆元—>tn———*an———tn-1——*an-1——>tn-2....——>t1

1  x     xy     xyz      xyzw
  1/x  1/xy   1/xyz    1/xyzw
 ai^-1 = si-1*ti
*/

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
unsigned int A, B, C;
int n,p;
const int N = 1e7+10;
int a[N];
ll s[N],t[N];

int exgcd(int a,int b,int &x,int &y)
{
  if(b==0)
  {
    x = 1,y = 0;
    return a;
  }
  int d = exgcd(b,a%b,y,x);
  y -= (a/b)*x;
  return d;
}

inline unsigned int rng61() {
    A ^= A << 16;
    A ^= A >> 5;
    A ^= A << 1;
    unsigned int t = A;
    A = B;
    B = C;
    C ^= t ^ A;
    return C;
}
int main() {
    scanf("%d%d%u%u%u", &p, &n, &A, &B, &C);
    int ans = 0;
    for (int i = 1; i <= n; i++)
    {
        a[i] = rng61()%p;
        if(a[i]==0)
        {
           a[i] = 1;
           ans^=1;
        }
    }
    s[0] = 1;
    for(int i = 1;i<=n;i++)s[i] = s[i-1]*a[i]%p;
    int x,y;
    /*
    求a在模mod时的逆元
    exgcd(a,mod,x,y);
    求出后,x就是逆元,mod可以不为质数
    */
    exgcd(s[n],p,x,y);//sn*x = 1(mod p)
    if(x<0)x+=p;
    t[n] = x;
    assert(s[n]*x%p==1);
    for(int i = n;i >= 1;i--)
      t[i-1]=t[i]*a[i]%p;
    for(int i = 1;i <= n;i++)
    {
        int v = s[i-1]*t[i]%p;
        ans^=v;
    }
    cout<<ans<<endl;
}

Nannan blog