初等数论Ⅰ

参考 smwcDay9 PPT by lby。

---

待补列表：

• 中国剩余定理的证明
• 欧拉定理（扩展）
• 埃氏筛的时间复杂度证明 $O(nloglogn)$ ？
• 扩展中国剩余定理 $excrt$ 的证明？ （from [CF 687B] Remainders Game)

---

整除

$a,b$ 都为整数，若 $a$ 被 $b$ 整除，相当于 $b$ 整除 $a$，则记 $b|a$ ，就有 $b$ 是 $a$ 的因数，$a$ 是 $b$ 的倍数。

性质

• 若 $a|b,a|c$，则 $a|(b+c),a|(b-c)$ ；
• 若 $a|b,b|c$，则 $a|c$ ;

[CF 762A] k-th divisor

link
题意
求 $n$ 的第 $k$ 小的约数，如果不存在输出 $-1$ 。  $1\le n\le 10^{15},1\le k\le 10^9$

思路
枚举 $n$ 的因数即可，找 $1$ ~ $\sqrt{n}$ 的因数，就能对应的找到 $>\sqrt{n}$ 的因数，时间复杂度为 $O(\sqrt{n})$ 。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e6+5;
ll g[maxn];
int main(){ll n,k; cin>>n>>k; int cnt=0; for(ll i=1;i*i<=n;i++)if(n%i==0){g[++cnt]=i;if(cnt==k){cout<<i;return 0;}}for(int i=cnt;i>=1;i--)if(n/g[i]!=g[i]){cnt++;if(cnt==k){cout<<n/g[i];return 0;}}cout<<"-1";return 0;
}

---

质数与合数

$1$ 既不是质数也不是合数。
不大于 $n$ 的质数约有 $\frac{n}{\ln (n)}$ 个。
唯一分解定理：把正整数 $n$ 写成质数的乘积（即 $n=p_1^{e_1}\times p_2^{e_2}\times p_3^{e_3}\times \cdots \times p_k^{e_k}$，其中 $p$ 为质数且单调递增），这样的表示是唯一的。

[CF 776B] Sherlock and his girlfriend

link
题意
$n$ 个点，标号为 $2\dots n+1$，将点染色，若 $a$ 是 $b$ 的质因子（$a\ne b$），则 $a$ 和 $b$ 的颜色不同，求一种颜色数最少的方案。   $n\le 1000$

思路
考虑将质数分在一个集合，合数分在另一个集合，分别染上不同颜色即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
bool isprm[maxn];
int main(){int n; cin>>n;cout<<(n<=2?"1\n":"2\n");for(int i=2;i<=n+1;i++){if(!isprm[i]) cout<<"1 ";else cout<<"2 ";for(int j=i+i;j<=n+1;j+=i)isprm[j]=1;}return 0;
}

---

带余除法，同余

对于整数 $a,b$，$b>0$，则存在唯一的整数 $q,r$，满足 $a=bq+r$。（$r=amodb$）
若两数 $a,b$ 除以 $c$ 的余数相等，则称 $a,b$ 模 $c$ 同余，记做 $a\equiv b(modc)$ 。
性质：$a\equiv b(modc)$ 等价于 $c|(a-b)$

---

最大公约数（gcd）

对于两个的整数 $a,b$，一般记 $gcd(a,b)=(a,b)$ 。
求最大公约数：$a=p_1^{a_1}{p}_2^{a_2}\dots p_k^{a_k}，b=p_1^{b_1}{p}_2^{b_2}\dots p_k^{b_k}$，有 $(a,b)=p_1^{min(a_1,b_1)}{p}_2^{min(a_2,b_2)}\dots p_k^{min(a_k,b_k)}$ 。

性质

• $(0,a)=a$
• $(a,b)=(a,a+b)=(a,ka+b)$
• $(ka,kb)=k\cdot (a,b)$
• $(a,b,c)=((a,b),c)$

[CF 664A] Complicated GCD

link
题意
求 $gcd(a,a+1,a+2,\dots ,b)$ 。  $1\le a\le b\le 10^{100}$

思路
注意到 $gcd(a,a+1)=1$ ，所以答案为 $1$，注意特判 $a=b$ 的情况。

[CF 757B] Bash’s Big Day

link
题意
给定 $n$ 个正整数 { a i } \{a_i\} {ai​}，求一个子集 $S$，满足 $gcd(S_1,S_2,...,S_k)>1$，同时 $|S|$ 尽可能大。$1\le n,a_i\le 10^5$

思路
考虑枚举 $d=gcd$ ，此时符合条件的集合为 { d , 2 d , 3 d … } \{d,2d,3d\dots\} {d,2d,3d…} 。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e5+5;
int v[maxn];
bool isprm[maxn];
int main(){int n; cin>>n; int ma=0;for(int i=1;i<=n;i++){int a; cin>>a;v[a]++,ma=max(ma,a);}int ans=1;for(int i=2;i<=ma;i++){if(isprm[i]) continue;int s=0;for(int j=i;j<=ma;j+=i)isprm[j]=1,s+=v[j];ans=max(ans,s);}cout<<ans;return 0;
}

欧几里德算法

又称为辗转相除法，用于快速计算两数的 $gcd$ 的算法。
由性质 $(a,b)=(a,ka+b)$ 得到：$(a,b)=(b,amodb)$
时间复杂度是 $O(logn)$ 。

---

裴蜀定理

设 $(a,b)=d$ ，则对任意整数 $x,y$ ，有 $d|(ax+by)$ 成立；特别地，一定存在 $x,y$ 满足 $ax+by=d$ 。
相当于 $ax+by=c$（$a,b,c$ 均为整数）有解的充要条件是 $(a,b)|c$ 。

推论

$a,b$ 互质等价于 $ax+by=1$ 有解。（即 $c=1$ 的情况）

扩展欧几里德算法（exgcd）

有 $(a,b)=d$，求解 $ax+by=d$ 。

• 求其中一组解：
  根据带余除法的定义，记 $a=bq+r$ 。原方程可转化成 $bx+ry=d$ （类似于辗转相除，$gcd(a,b)=gcd(b,amodb)$）。记新方程的一个解为 $x=x_0,y=y_0$，考虑如何推回原方程的解。
  将 $a=bq+r$ 代入原方程 $ax+by=d$ 中，化简得 $(qx+y)b+rx=d$，令 $qx+y=x_0,x=y_0$，上式成立。
  故 $x=y_0,y=x_0-q\times y_0$ 即为原方程的解。注意当 $b=0$ 时，令$x=1,y=0$。
• 求所有解：
  因为我们已经有了一组解 $x_0,y_0$，令 $d_x=\frac{b}{(a,b)},d_y=-\frac{a}{(a,b)}$。
  则所有解就是 $x=x_0+k{d}_x,y=y_0+k{d}_y$，$k$ 取任意整数。

LG P4549 【模板】裴蜀定理

link
题意
给定整数 { a 1 , a 2 , a 3 , . . . , a n } \{a_1, a_2, a_3, ..., a_n\} {a1​,a2​,a3​,...,an​} 和 $k$ ，有一个待定整数序列 $x_1,x_2,x_3,...,x_n$，满足$a_1{x}_1+a_2{x}_2+a_3{x}_3+...+a_n{x}_n=k$，求 $k>0$ 且 $k$ 尽量小。  $1\le n\le 20,|A_i|\le 10^5$

思路
根据裴蜀定理，有 $gcd(a_1,a_2,a_3,\dots ,a_n)|k$ ，所以 $k_{min}=gcd(a_1,a_2,\dots ,a_n)$ 。

---

逆元

若 $ax\equiv 1(modb)$，则称 $x$ 是 $a$ 关于模 $b$ 的逆元，常记做 $a^{-1}$。
根据同余的性质，上式等价于 $ax+by=1$，如何求逆元？等价于解方程 $ax+by=1$ 。
因此逆元不一定存在：存在的充要条件为 $(a,b)=1$ 。

推论

$p是质数，p不整除a，则a模p的逆元存在。$

结论：在 $[0,b)$ 的范围内，$a$ 关于模 $b$ 的逆元（若存在）是唯一的。（证明可考虑反证法）

如何 $O(n)$ 求 $1$ ~ $n$ 模质数 $p$ 的逆元 ？

• 方法一：倒推
  先求出 $n!$ 的逆元，然后利用 $(k-1){!}^{-1}\equiv k\times k{!}^{-1}(modp)$，倒推求出 $1!\dots (n-1)!$ 的逆元，再利用 $k^{-1}\equiv (k-1)!k{!}^{-1}(modp)$，就可以求出 $\mathrm{1...}n$ 的逆元了。
• 方法二：递推
  现在求 $i$ 的逆元，考虑带余除法，设 $p=iq+r$ ，则有 $iq+r\equiv 0(modp)$，注意到 $p$ 是质数，因此 $r$ 不为0，$r$ 的逆元存在。等式两边乘 $i^{-1}{r}^{-1}$，得到 $q{r}^{-1}+i^{-1}\equiv 0(modp)$，因此$i^{-1}\equiv -q{r}^{-1}\equiv -\frac{n}{i}(pmodi{)}^{-1}(modp)$ 。
  inv[1]=1; for(int i=2;i<=n;i++) inv[i] = (- p / i + p) * inv[p % i] % p;

---

中国剩余定理（CRT）

形如 $ax\equiv c(modb)$ 的方程，称为 线性同余方程。等价于 $ax+by=c$，因此有解条件为 $(a,b)|c$ 。
中国剩余定理：对于同余方程组 $x\equiv a_i(mod{m}_i)(i=\mathrm{1...}n)$，若 $m_i$ 两两互质，则 $x$ 在 $modM$下有唯一解。这里 $M=m_1{m}_2...m_n$ 。

构造解的方法：
令 $M_i=\frac{M}{m_i}$，显然 $(M_i,m_i)=1$，所以 $M_i$ 关于模 $m_i$ 的逆元存在，把这个逆元设为 $t_i$。
于是有 $M_i{t}_i\equiv 1(mod{m}_i),M_i{t}_i\equiv 0(mod{m}_j)(j\ne i)$ ，
进一步 $a_i{M}_i{t}_i\equiv a_i(mod{m}_i),a_i{M}_i{t}_i\equiv 0(mod{m}_j)(j\ne i)$ ，
因此解为 $x\equiv a_1{M}_1{t}_1+a_2{M}_2{t}_2+...+a_n{M}_n{t}_n(modM)$ 。

例题：组合数取模2

题意
$T$ 次询问，每次询问 $C(n,k)mod1029471131（1029471131=13\times 317\times 249811)$   $T\le 10^5,0\le k\le n\le 10^{18}$

思路
分别将 $C(n,k)$ 对 $13,317,249811$ 取模，再用中国剩余定理合并。
如何求 $C(n,k)modp$ （其中 $p$ 为较小的质数）？
$\ast Lucas定理：$设 $p$ 为质数，则 $C_n^k\equiv C_{\lfloor \frac{n}{p}\rfloor }^{\lfloor \frac{k}{p}\rfloor }\times C_{(nmodp)}^{(kmodp)}(modp)$ 。

---

欧拉函数

$\phi (n)$ 定义为 $[1,n]$ 中与 $n$ 互质的数的个数。
欧拉函数是积性函数：若 $(a,b)=1$ ，则 $\phi (ab)=\phi (a)\phi (b)$ 。

• $若n=p^k，p为质数，则\phi (n)=n\times (1-\frac{1}{p})$ 。
  证明：若 $(x,p^k)>1$，则有 $p|x$ 成立，$x$ 共有 $\lfloor \frac{n}{p}\rfloor$个，因此 $\phi (n)=n-\lfloor \frac{n}{p}\rfloor =n\times (1-\frac{1}{p})$
• $若n所有不同的质因子为p_1,p_2,...,p_k，则\phi (n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k})$ 。

[SDOI2012]Longge的问题

link
题意
求 $\sum _{i=1}^{n}gcd(i,n)$，$n\le 2^{32}$ 。

思路
注意到 $gcd(i,n)$ 一定是 $n$ 的约数， $n$ 的约数不多于 $\sqrt{n}$ 个。考虑枚举 $n$ 的约数（设为 $d$ ），再求出满足 $gcd(i,n)=d$ 的 $i$ 有多少个。
显然不能是 $\frac{n}{d}$，会算多。考虑将 $gcd(i,n)=d$ 转化成 $gcd(\frac{i}{d},\frac{n}{d})=1$。因为 $1\le i\le n$，所以 $1\le \frac{i}{d}\le \frac{n}{d}$ 。个数就是求 $[1,\frac{n}{d}]$ 中与 $\frac{n}{d}$ 互质的个数，即 $\phi (\frac{n}{d})$ 。答案即为 $\sum _{d|n}d\times \phi (\frac{n}{d})$ 。时间复杂度约为 $O(n^{0.5})$ 。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;int Get_phi(ll x){ll phi=x;for(ll i=2;i*i<=x;i++)if(x%i==0){while(x%i==0) x/=i;phi/=i,phi*=(i-1);//不能写成 phi*=(i-1)/i !!}if(x>1) phi/=x,phi*=(x-1);return phi;
}int main(){ll n; cin>>n;ll ans=0;for(ll i=1;i*i<=n;i++)if(n%i==0){ans+=Get_phi(n/i)*i;if(n/i!=i) ans+=Get_phi(i)*(n/i);}cout<<ans;return 0;
}

[Sdoi2008]沙拉公主的困惑

link
题意
回答 $T$ 组询问：每组询问 $[1,n!]$ 中与 $m!$ 互质的数的个数，结果对 $r$ 取模。$1\le m\le n\le 10^7，1\le T\le 10^4，2\le r\le 10^9+10且r为质数。$

思路
因为有 $gcd(i,m!)=gcd(m!\times k+i,m!)$，所以对于所有 $\forall k\in [1,\frac{n!}{m!}],[(k-1)\times M!+1,k\times M!]$ 中与 $m!$ 互质的数是相等的。所以答案为 $\frac{n!}{m!}\times \phi (m!)$。
考虑如何求 $ans=\frac{n!}{m!}\times \phi (m!)$ 。
因为 $\phi (n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k})$，将 $m!$ 代入得，$ans=n!\times (1-\frac{1}{p_1})(1-\frac{1}{p_2})...(1-\frac{1}{p_k})$ （这里 $p_1...p_k$ 为 $m!$ 的所有质因子，即不大于 $m$ 的所有素数。)
化简得：$ans=n!\times \frac{\prod (p_i-1)}{\prod p_i}$。 线性求逆元、质数，预处理即可。注意模数 $r$ 有可能小于 $m,n$，此时 $n!$ 和 $\frac{1}{\prod p_i}$ 中会消去一个 $r$ 。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e7+5,N=1e7;
int prm[maxn],fac[maxn],g[maxn],inv[maxn],invp[maxn];//不要开太多 ll，会 MLE 
bool isprm[maxn];
int main(){int t,mod; cin>>t>>mod;inv[1]=1;for(ll i=2;i<=N;i++)inv[i]=1ll*(-mod/i+mod)*inv[mod%i]%mod;isprm[1]=fac[1]=g[1]=invp[1]=1;int pn=0;for(ll i=2;i<=N;i++){fac[i]=(i!=mod?1ll*fac[i-1]*i%mod:fac[i-1]);g[i]=g[i-1],invp[i]=invp[i-1];if(!isprm[i]){prm[++pn]=i;g[i]=1ll*g[i]*(i-1)%mod;//注意 ll ，不能写成 (g[i]*=1ll*(i-1))%=mod ！！！ if(i!=mod) invp[i]=1ll*invp[i]*inv[i]%mod; }for(int j=1;j<=pn&&i*prm[j]<=N;j++){isprm[i*prm[j]]=1;if(i%prm[j]==0) break;}}while(t--){int n,m; cin>>n>>m;if(n>=mod&&m<mod) cout<<"0\n";//若因子 mod 抵消不了，%mod 后就会为 0 else cout<<1ll*fac[n]*g[m]%mod*invp[m]%mod<<"\n";//！！！参考 https://www.luogu.com.cn/article/al267pxj }return 0;
}

欧拉定理

若 $(a,n)=1$，则 $a^{\phi (n)}\equiv 1(modn)$ 。

求逆元：$a\times a^{\phi (n)-1}\equiv 1(modn)$；特别地，若 $n$ 是质数 $a\times a^{n-2}\equiv 1(modn)$ 。

欧拉定理的扩展

定理：$a^{2\phi (n)}\equiv a^{\phi (n)}(modn)$
推论：当 $b\ge \phi (n)$ 时，$a^b\equiv a^{(bmod\phi (n))+\phi (n)}(modn)$

LG P4139 上帝与集合的正确用法

link
题意
令 $a_n=\stackrel{n个2}{\overbrace{2^{2^{2^{2^{\dots }}}}}}$ ，求 $\underset{n\to \infty }{\lim }(a_{n}modm)$ 。  $T\le 10^3,p\le 10^7$

思路
题目说明了存在 $\underset{n\to \infty }{\lim }(a_{n}modm)$ 。
又因为有结论 $2^{a_n}\equiv 2^{(a_{n}mod\phi (m))+\phi (m)}(modm)$，所以问题转化成求 $\underset{n\to \infty }{\lim }(a_{n}mod\phi (m))$ 。
由于 $\phi (m)$ 的 $m$ 会越来越小，$m=1$ 时终止递归（开始回退），此时 $\phi (m)=1$ ，那么 $(a_{n}mod1)=0$ 。
可以证明递归的层数不大于 $2lo{g}_{2}m$ ，总时间复杂度为 $O(\sqrt{n})$ 。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;int Phi(int x){int phi=x;for(ll i=2;i*i<=x;i++)if(x%i==0){while(x%i==0) x/=i;phi/=i,phi*=(i-1);}if(x>1) phi/=x,phi*=(x-1);return phi;
}int Pow_(ll x,ll y,ll mod){ll s=1;while(y){if(y&1) (s*=x)%=mod;(x*=x)%=mod;y>>=1;}return s;
}int Func(int m){if(m==1) return 0;int phi_m=Phi(m);return Pow_(2,Func(phi_m)%phi_m+phi_m,m);
}int main(){int t; cin>>t;while(t--){int mod; cin>>mod;cout<<Func(mod)<<"\n";}return 0;
} 

---

线性筛与积性函数

$Q$：如何 $O(n)$ 求 $[1,n]$ 的素数？
$A$：每个合数必须只被筛去一次，考虑 $dp$ 求 $[1,n]$ 每个数的最小质因子，则每个合数在枚举到自己最小的质因子得时候被筛去即可。

积性函数：$f(1)=1$ 。若 $(a,b)=1$, 则 $f(ab)=f(a)f(b)$ 。
常见的积性函数：

• $\phi (n)$：欧拉函数
• $d(n)$：约数个数
• ${\sigma }_k(n)$：约数的k次幂和

$Q$：给定积性函数 $f$，如何求 $f(1)...f(n)$ 的值？
$A$：利用积性，设 $n=p^k{n}^{\prime }$（ $p$ 是 $n$ 最小的质因子，$k$ 是 $p$ 在 $n$ 中的次数）则有$f(n)=f(p^k)f(n^{\prime })$ 。只需特别考虑 $f(p^k)$；其它用线性筛递推即可。

LG P2568 GCD

link
题意
给定正整数 $n$，求 $1\le x,y\le n$ 且 $\gcd (x,y)$ 为素数的数对 $(x,y)$ 有多少对。  $1\le n\le 10^7$

思路
由题得， $gcd(x,y)=d$ （$d$ 为质数）。令 $x^{\prime }=\frac{x}{d},y^{\prime }=\frac{y}{d}$，又有 $gcd(x\prime ,y\prime )=1$ 。

• 若 $x\prime \ge y\prime$，有 $\phi (x\prime )$ 个 $y\prime$ 满足 $gcd(x\prime ,y\prime )=1$；
• 若 $x\prime \le y\prime$，有 $\phi (y\prime )$ 个 $x\prime$ 满足 $gcd(x\prime ,y\prime )=1$；
• 若 $x\prime =y\prime$，只有 $1$ 种情况，$x\prime =1,y\prime =1$；

所以对于任意 $d$，满足 $gcd(x,y)=d$ 的个数有 $(2\times \sum _{i=1}^{\frac{n}{d}}\phi (i))-1$ 个。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e7+5;
int prm[maxn],phi[maxn];
ll sum[maxn];
bool isprm[maxn];
int main(){int n; cin>>n;phi[1]=1;int pn=0;for(ll i=2;i<=n;i++){if(!isprm[i]) prm[++pn]=i,phi[i]=i-1;for(int j=1;j<=pn&&i*prm[j]<=n;j++){int k=i*prm[j]; isprm[k]=1;if(i%prm[j]==0){phi[k]=phi[i]*prm[j];break;}else phi[k]=phi[i]*phi[prm[j]];}}for(int i=1;i<=n;i++)sum[i]=sum[i-1]+phi[i];ll ans=0;for(int i=1;i<=pn;i++)ans+=2*sum[n/prm[i]]-1;cout<<ans;return 0;
}

例题2

题意
求 $\sum _{i=1}^n\sum _{j=1}^n(-1{)}^{d(ij)}$，$d(n)$ 表示 $n$ 的约数个数。$1\le n\le 10^7$

思路
由题目可知，若某个数的约数个数为奇数，取 $-1$；否则取 $1$。
$发现，只有完全平方数的约数个数才会为奇数。$
考虑当为完全平方数时 $i,j$ 有什么特点。设 $i=a\times b^2$，其中 $a$ 不能被大于 $1$ 的完全平方数整除。设 $f(i)=a$，则如果 $i\times j$ 为完全平方数时，$f(i)=f(j)$。
所以只需统计 $f(1)\dots f(n)$ 中每种数的出现次数即可。
又发现，$f()$ 为积性函数，特殊处理 $f(p^k)=p^{kmod2}$ ，用线性筛即可求出 $f()$ 。

---

补充题

[SDOI2009] SuperGCD

link
题意
给出两个整数 $a,b$，求 $gcd(a,b)$ 。   $0<a,b\le 10^{10000}$

思路
如果直接用辗转相除法，就需要实现高精度除法，复杂度会有问题。
考虑按 $奇偶$ 分类：

• 若 $a,b$ 同为偶数，则 $(a,b)=2\times (\frac{a}{2},\frac{b}{2})$ ；
• 若 $a,b$ 同为奇数，不妨设 $a>b$ ，则 $(a,b)=(\frac{a-b}{2},b)$ ；
• 若 $a,b$ 一奇一偶，不妨设 $a$ 为偶数，则 $(a,b)=(\frac{a}{2},b)$ ；

只会经过 $log$ 次迭代，每次操作只有 $/2,\times 2,-$，用高精度即可。
注意卡常，递归会 $mle$，建议改成递推。可以使用压位高精。

代码
卡常中……

[Violet 5] 樱花

link
题意
求 $\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$ 的正整数解 $(x,y)$ 的个数。$n\le 10^6$，答案对 $10^9+7$ 取模。

思路
设 $z=n!$ ，推一推式子就有 $(x-n!)(y-n!)=z^2$ ，即 $a=x-n!,b=y-n!$，原始又转化为 $ab=z^2$ 。
若 $a,b$ 为正整数，则 $x,y$ 也一定为正整数。所以就是求 $z^2$ 的因数个数。
$z^2=(n!{)}^2$，$(n!{)}^2$ 的质因数不大于 $n$。
由唯一分解定理得：$(n!{)}^2=p_1^{e_1}{p}_2^{e_2}\dots$ 。所以 $(n!{)}^2$ 得因数个数为：$(2e_1+1)(2e_2+1)\dots$ 。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=1e6+5,mod=1e9+7;
int prm[maxn],gy[maxn];
ll f[maxn];
bool isprm[maxn];
int main(){ll n; cin>>n;int pn=0;for(ll i=2;i<=n;i++){if(!isprm[i]){prm[++pn]=i;gy[i]=i;//gy[i]：i 的最大质因子 }for(int j=1;j<=pn&&i*prm[j]<=n;j++){isprm[i*prm[j]]=1;gy[i*prm[j]]=prm[j];//不能放在 if 的下面！！ if(i%prm[j]==0) break;}}for(int i=1;i<=n;i++)for(int j=i;j>1;j/=gy[j])f[gy[j]]++,f[gy[j]]%=mod;ll ans=1;for(int i=1;i<=pn;i++)(ans*=(f[prm[i]]*2+1))%=mod;//求 (n!)^2 的因子个数 cout<<ans;return 0;
}

[CF 632D] Longest Subsequence

link
题意
给出 $n$ 个数，要求选出尽可能多的数，满足它们的最小公倍数不大于 $m$ 。$1\le n,m\le 10^6,1\le ai\le 10^9$

思路
考虑枚举 $lcm$ 。由于选出的数一定为 $lcm$ 的约数，所以可以设 $f[i]$ 表示 $i$ 的约数在 { a } \{a\} {a} 中有出现的个数。但是 $f[]$ 不是积性函数，也就只能用埃氏筛求。时间复杂度约为 $O(nloglogn)$ 。$(不知道怎么证明?)$

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=1e6+5;
int a[maxn],b[maxn],f[maxn],f2[maxn];
int main(){int n2,m,n=0; cin>>n2>>m;for(int i=1;i<=n2;i++){cin>>b[i];if(b[i]<=m){if(!f2[b[i]]) a[++n]=b[i];f2[b[i]]++;}}
/*     不能用线性筛！！！
因为 d[i] 表示 i 的约数个数时是积性函数，但是 f[i] 表示 i 的约数在 {a} 中有出现的个数，这并不是积性函数。 
*/for(int i=1;i<=n;i++)for(int j=a[i];j<=m;j+=a[i])f[j]+=f2[a[i]];int ans=1;//此题中，空集的 lcm 等于 1 ！！ for(int i=2;i<=m;i++)if(f[i]>f[ans]) ans=i;cout<<ans<<" "<<f[ans]<<"\n";for(int i=1;i<=n2;i++)if(ans%b[i]==0) cout<<i<<" ";return 0;
}

[CF 582A] GCD Table

link
题意
对一个长度为 $n$ 的数列 $a$ ，定义它的 GCD Table G 是一张 $n\times n$ 的二维表，其中 $G_{i,j}=gcd(a_i,a_j)$ 。现在乱序给出 $G$ 中所有 $n^2$ 个数，求原数列 $a$ 。$1\le n\le 500,G_{i,j}\le 10^9$

思路
分析发现，$G$ 中最大的数一定也是 $a$ 中最大的数，$G$ 中次大的数一定也是 $a$ 中次大的数，第三、第四可能是由 $a$ 中最大和次大的 $gcd$ 产生的。但是对于已经确定的 { a } \{a\} {a} 我们可以先消掉他们之间的 $gcd$，剩下的 $G$ 就变成了一个子问题，同样策略求解即可。

代码

#include<bits/stdc++.h>
using namespace std;
const int maxn=505;
int a[maxn],g[maxn*maxn];
map<int,int>mp;
int main(){int n; cin>>n;for(int i=1;i<=n;i++)for(int j=1;j<=n;j++){int x; cin>>x; g[(i-1)*n+j]=x,mp[x]++;}sort(g+1,g+n*n+1,[](int a,int b){ return a>b; });for(int i=1,j=1;i<=n;i++){while(!mp[g[j]]) j++;a[i]=g[j],mp[g[j]]--;for(int k=1;k<i;k++)mp[__gcd(a[i],a[k])]-=2;}for(int i=1;i<=n;i++)cout<<a[i]<<" ";return 0;
} 

[CF 687B] Remainders Game

link
题意
给定正整数 $n,k$ 和 $n$ 个正整数 $c_1,c_2,\dots ,c_n$ 。如果对于任意正整数 $x$，可以通过 $xmod{c}_i$ 的值推出 $xmodk$ 的值则输出 Yes ，否则输出 No。  $1\le n,k,c_i\le 10^6$

思路
容易猜出结论：当且仅当 $k|lcm(c_1,c_2,...,c_n)$ 时，输出 Yes；（证明参考扩展中国剩余定理 $excrt$）
方法一：将 $k,lcm$ 都分解质因数，再比较两者质因数的次数；
方法二：在求 $lcm$ 的时候加上取模，防止溢出。（这个比较好写）
可能要卡卡常。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;ll Get_gcd(ll a,ll b){ return !b?a:Get_gcd(b,a%b); }
ll Get_lcm(ll a,ll b){ return a*b/Get_gcd(a,b); }inline int read(){int x=0,f=1; char c=getchar();while(c<'0'||c>'9'){ if(c=='-') f=-1; c=getchar(); }while(c>='0'&&c<='9'){ x=(x<<3)+(x<<1)+c-'0'; c=getchar(); }return x*f;
}int main(){int n=read(),k=read(); ll d=1;for(int i=1;i<=n;i++){int c=read();d=Get_lcm(d,c)%k;}cout<<(d%k==0?"Yes":"No");return 0;
}

---

总结

简化题目，将其转化为式子（数）进行推导，得出性质。