【全程NOIP计划】简单数论

基础知识与记号

$\forall$,$\exist$

整除：如果$a=bk $,其中$a,b,k$都是整数，则$b$整除$a$，记作$b|a$

也称作b是a的约数（因数），a是b的倍数

如何求出n的所有约数？

如果a是n的约数，则n/a也是n的约数，且a和n/a中必有一个小于等于根号n

所以我们直接枚举1到根号n之间的所有数，判断是不是n的因数就可以了

a和b的最大公因数记为$\gcd(a,b)$,或者$(a,b)$

特殊地

1.$(a,a)=(0,a)=a$

2.如果$a|b$，则$(a,b)=a$

3.$(a,b)=(a,a+b)=(a,ka+b),(a,b)=(b,a \space mod \space b)$

4.$(ka,kb)=k*(a,b)$

5.$(a,b,c)=((a,b),c)$

6.如果$(a,b)=1$则称a和b互质，记为$a \bot b$

对于整数a,b,$b>0$，则存在唯一的整数q,r，满足$a=bq+r$，其中$0 \leq r <b$

$a \div b = q \dots \dots r$

其中称q为商，r为余数，余数r用$a \space mod \space b$表示

如果有两个整数a满足除以b的余数为r，则我们称$a \equiv a'(mod \space b)$

唯一分解定理

对于一个整数n，它可以唯一分解成$n= \prod p_i^{k_i}$

例如36可以唯一分解为$36=2^2 \times 3^2$

定义域为整数的函数被称为数论函数

对于数论函数$f$

1.如果$\forall a\bot b ,f(ab)=f(a)f(b)$，则称$f$为积性函数

2.如果$\forall a,b,f(ab)=f(a)f(b)$，则称$f$为完全积性函数

例如$f(x)=x$就是一个完全积性函数

欧几里得算法

给定$a，b$，快速算出$(a,b)$

引理：若$a<b$,则$b \space mod \space a<b/2$

不断运用$(a,b)=(a,b\space mod \space a)$,直到某个数为0

至少运行$\log_2^a$次或者$log_2^b$次，就会有某个数变成0

int gcd(int a,int b)
{
    return b? gcd(b,a%b):a;
}

拓展欧几里得算法

裴蜀定理

$\forall a,b, \exist x,y,s.t. ax+by=(a,b)$

使用构造法来证明这个东西

当b=0时，x=1，y=0

否则：
$
ax+by

\=(\lfloor \frac a b \rfloor*b+a \mod b)x+by
\=b(y+\lfloor \frac a b \rfloor x)+(a\mod b)
\=gcd(a,b)
$如果已经求出来$bx’+(a \mod b)y’=gcd(a,b)$的解，则$x=y’,y=x’-\lfloor \frac a b \rfloor y’$

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

如何求出$ax+by=(a,b)$所有的解？

先用exgcd求出一组x0,y0

其他的解为:$x=x_0+k \frac b {(a,b)},y=y_0-k \frac a {(a,b)}$

其中最小的正数x为$(\frac b {(a,b)}+x_0 \mod \frac b {(a,b)}) \mod \frac b {(a,b)}$

欧拉函数

$\phi(n)$表示1~n中与n互质的数的个数，称为欧拉函数

例如1~12中，1,5,7,11和12互质，则$\phi(12)=4$

怎么求？

设$n =\prod p_i^{k_i}$则$\phi(n)=n \prod(1-\frac 1 {p_i})=\prod p_i^{k_i-1}*(p_i-1)$

枚举质因子计算就可以了，时间复杂度$O( \sqrt{n})$

(拓展)欧拉定理（欧拉函数）

欧拉定理：$\forall a \bot b ,a^{ \phi (n)} \equiv 1 (\mod n)$

拓展欧拉定理：$\forall a,n,a^{2 \phi(n)} \equiv a^{\phi (n)}(mod \space n)$

也就是说，$b> \phi(n) \to a^b \equiv a^{b \space mod \space \phi(n)+\phi(n)}(mod \space n)$

P5110 块速递推

思路

先运用拓展欧拉定理 ，将b缩小到$2\phi(c)<2c$的范围之内

$a^b=(a^{ \sqrt{c}})^{\lfloor \frac b {\sqrt{c}}\rfloor}*a^{b \space mod \space c}$，其中$\lfloor \frac b {\sqrt{c}} \rfloor <2 \sqrt{c},b \space mod \space \sqrt{c}< \sqrt{c}$

预处理$(a^{\sqrt{c}})^i,a^j(1\le i \le 2\sqrt{c},1 \le j <\sqrt{c})$即可

实际上是一种分块的做法

可以预处理，然后再直接查询

实际上就是光速幂，具体模板题为LOJ.162.快速幂 2

通过题目给定的递推公式，我们首先可以推出来一个用来递推的矩阵
$X=\begin{bmatrix} 233 & 1 \\ 666 & 0 \end{bmatrix}$
然后预处理一下

最后对于每个n，直接通过预处理的数据直接$O(1)$输出

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
#include <cmath>
using namespace std;
const int maxn=50005;
const int p=1e9+7;
unsigned long long T,res;
namespace Mker
{
    unsigned long long SA, SB, SC;
    void init()
	{
		scanf("%llu%llu%llu", &SA, &SB, &SC);
	}
    unsigned long long rand()
    {
        SA ^= SA << 32, SA ^= SA >> 13, SA ^= SA << 1;
        unsigned long long t = SA;
        SA = SB, SB = SC, SC ^= t ^ SA; return SC;
    }
}
struct matrix 
{
    long long a,b,c,d;
    matrix()
	{
		a=b=c=d=0;
	}
    matrix operator *(register matrix &s)
    {
        matrix temp;
        temp.a=(a*s.a+b*s.c)%p;
		temp.b=(a*s.b+b*s.d)%p;
        temp.c=(c*s.a+d*s.c)%p;
		temp.d=(c*s.b+d*s.d)%p;
        return temp;
    }
}base,m1[maxn],m2[maxn];

int main()
{
	cin>>T;
	Mker::init();
	//初始化矩阵 
    base.a=233;
	base.b=666;
	base.c=1;
	/*进行矩阵递推*/
    m1[1]=base;
	int len=sqrt(1e9+6);
    for(int i=2;i!=len;i++)
	m1[i]=m1[i-1]*base;
	
    m2[1]=m1[len-1]*base;
	m1[0].a=m1[0].d=1;
    m2[0].a=m2[0].d=1;
    
	for(int i=2;i<=len+1;i++)
	m2[i]=m2[i-1]*m2[1];
	
    while(T--)
    {
        matrix ans;
		ans.a=1;
        int n=Mker::rand()%1000000006;
        if(n<=1)
		res^=n;
        else
        {
        	ans=ans*m2[(n-1)/len]*m1[(n-1)%len];
			res^=ans.a;
		}
    }
    cout<<res<<'\n'; 
    return 0;
}

逆元

如果$ax \equiv 1(mod \space b)$，则称x为a关于模b的逆元，通常记作$a^{-1}$

分数取模:$\frac ab \equiv a*b^{-1}(mod \space p)$,

$a^{-1}$存在的充要条件是$(a,b)=1$

在$[0,b)$的范围诶，a关于模b的逆元（如果存在的话），是唯一的

等价于求$ax+by=1$，课可以直接使用拓展欧几里得解决

如果b是质数，则$\phi(b)=b-1,a*a^{b-2}=a^{b-1}\equiv 1(mod \space b)$,所以逆元为$a^{b-2}$，使用快速幂计算

如何在$O(n)$的时间内求1~n内的模质数p的所有逆元呢？

$i^{-1} \equiv - \lfloor \frac pi \rfloor (p \space mod \space i)^{-1} \iff p \space mod \space i \equiv -\lfloor \frac pi \rfloor *i \iff \lfloor \frac pi \rfloor *i+p \space mod \space i =p \equiv (mod \space p) $

威尔逊定理

$(p-1)! \equiv -1 (mod \space p)$

$x^2 \equiv 1 (mod \space p)$的解仅有$x \equiv 1,x \equiv -1(mod \space p)$

所以2~p-2和逆元两两对应

剩下$1*(p-1) \equiv -1 (mod \space p)$

中国剩余定理

求解x，满足方程组
\bbox[yellow]{ \begin{cases} x \equiv 2 & \text{(mod 3)} \\ x \equiv 3 & \text{(mod 5)} \\ x \equiv 2 & \text{(mod 7)} \\ \end{cases} }
令$M=m_1m_2\dots m_n,M_i=M/m_i$

显然有$(M_i,m_i)=1$，所以$M_i$关于模$m_i$的逆元存在，把这个逆元设为$t_i$

于是有$M_it_i \equiv 1 \text{(mod m)},M_it_i \equiv 0 (mod \space m_j)(j \not= i)$

进一步有$a_iM_it_i \equiv a_i(mod \space m_i),a_iM_it_i \equiv 0 (mod \space m_j)(j \not= i)$

因此解为$x \equiv a_1M_1t_1+a_2M_2t_2+\dots \dots a_nM_nt_n(mod \space M)$,且在模m意义下唯一解

拓展中国剩余定理

求解x，满足方程组$x \equiv a_i(mod \space m_i)$，其中$m_i$不一定两两互质

同样的，在mod $lcm(m_i)$的意义下有唯一解

考虑如何每次将两个方程$\begin{cases} x \equiv a_1 \space mod \space m_1 \x \equiv a_2 \space mod \space m_2\end{cases} $合并成一个方程$x \equiv a(mod \space m =lcm(m_1,m_2))$$
\begin{cases} x\equiv a_1(mod \space m_1) \
x\equiv a_2(mod \space m_2)\end{cases} \iff
\begin{cases} x=a_1+k_1m_1 \
x=a_2+k_2m_2\end{cases}
\iff k_1m_1-k_2m_2=a_2-a_1
$先用拓展欧几里得算法求出$k_1m_1-k_2m_2=gcd(m_1,m_2)$的一组特解$K_1,K_2$

$ \begin{cases} x=a_1+K_1 \frac {a_2-a_1} {gcd(m_1,m_2)}m_1 \ x=a_2+K_2 \frac {a_2-a_1}{gcd(m_1,m_2)}m_2 \end{cases}$可以发现两个不同的解x的差一定是$lcm(m_1,m_2)$的倍数

所以$x \equiv a_1+K_1 \frac{a_2-a_1}{gcd(m_1,m_2)}=a_2+K_2 \frac {a_2-a_1}{gcd(m_1,m_2)}m_2(mod \space lcm(m_1,m_2))$

其他常见的积性函数

$\mu(n)=\begin{cases} 0,&\text{0有平方因子} \\(-1)^k &\text{n无平方因子，k为n的质因数个数} \end{cases}$

$\sigma_k(n)=\sum_{i|n}i^k$,$\sigma_0(n)$又写作$d(n)$表示n的约数个数（除数函数）

$gcd(n,k)$

完全积性函数：

$1(n)=1,id_k(n)=n^k,\epsilon(n)=\begin{cases} 1,n=1 \\0,n \not-1\end{cases}$

$N_{\delta}= \prod_pp^{\lfloor \frac 1 {p^{\delta}-1} \rfloor},N_{\delta}$显然收敛

当$n>N_{\delta}$时，有：$d(n)<n^{(1+\delta)\frac {log2}{log\space logn}}$

普通筛法

以下整数，代指>1的整数

基本思想：整数的整数倍是合数，时间复杂度$O(nlogn)$

for(int i=2;i<=n;i++)
{
    if(!vis[i])
        p[++t]=i;
    for(int j=2*i;j<=n;j+=i)
        vis[j]=1;
}

埃氏筛

基本思想:素数的整数倍数为合数，时间复杂度$O(n\space log \space logn)$

for(int i=2;i<=n;i++)
{
    if(!vis[i])
    {
        p[++t]=i;
        for(int j=2*i;j<=n;j+=i)
            vis[j]=true;
    }
}

线性筛

基本思想：整数的素数倍数是合数

枚举整数的素数倍数，当枚举到的素数是当前整数的因数时候停止

设n的最小值因子为$p_n$，n会且仅在$i=n/p_n$倍筛到

for(int i=2;i<=n;i++)
{
    if(!vis[i])
        p[++t]=i;
    for(int j=1;j<=t&&i*p[j]<=n;j++)
    {
        vis[i*p[j]]=1;
        if(i%p[j]==0)
            break;
    }
}

区间筛

求$[a,b]$中的所有质数，$a,b \leq 10^{12},b-a \leq 10^6$

基本思想：埃氏筛

1.先筛出$1到 \sqrt{b}$的所有质数

2.用这些质数筛去$[a,b]$中的合数

线性筛求积性函数

对于每个合数n，在线性筛的过程中都会拆成$\frac n {p_n}$和$p_n$

设$(p_n^{\inf},n)=p_n^k$,则$\frac n {p_n^k}$和$p_n^k$是互质的

1.算出$f(p_n^k)$

2.对于其他合数，$f(n)=f(\frac n {p_n^k})*f(p_n^k)$

//phi
for(int i=2;i<=n;i++)
{
    if(!vis[i])
    {
        p[++t]=i;
        phi[i]=i-1;
    }
    for(int j=1;j<=t&&i*p[j]<=n;j++)
    {
        vis[i*p[j]]=true;
        if(i%p[j])
            phi[i*p[j]]=phi[i]*(p[j]-1);
        else
        {
            phi[i*p[j]]=phi[i]*p[j];
            break;
        }
    }
}

P2303 Longge的问题

思路

1.直接计算可以得65分，非常良心

我们设 $t(x)$ 为 $1 - n$ 中与 $n$ 的最大公因数为 $x$ 的数的个数，即

$t(x) = \sum_{i = 1}^n[\gcd(i, n) = x] = \sum_{i = 1}^{\lfloor\frac nx\rfloor}[\gcd(i, \lfloor\frac nx\rfloor) = 1]$
考虑 $\phi(x) = \sum\limits_{i = 1}^n[gcd(i, n) = 1]$
即 $t(x) = \phi(\lfloor\frac nx\rfloor)$
由于$\gcd(i, n) | n$，考虑化简原式为：
$\sum_{i = 1}^n\gcd(i, n) = \sum_{d|n}d\sum_{i = 1}^n[\gcd(i, n) = d] = \sum_{d|n}d\phi(\frac nd)$
对于所有 $d | n$ 可以在 $O(\sqrt n)$ 的时间复杂度内枚举，$\phi$ 函数可以在 $O(\sqrt n)$ 的时间复杂度内求出，故时间复杂度为 $O(因数个数 * \sqrt n)$

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <string>
using namespace std;
long long n;
int main()
{
    scanf("%lld",&n);
    long long ans=n;
    for(register long long i=2;i*i<=n;++i) 
    {
    	if(n%i==0)
		{
        	int b=0;
      	 	while(n%i==0) 
			{
				b++;
				n/=i;  	
			}
        	ans/=i;
       		ans*=b*i-b+i;
    	} 
	}
	if(n>1)
	{
		ans/=n;
		ans*=n+n-1;
	}
    printf("%lld",ans);
    return 0;
}

CF757B Bash’s Big Day

思路

$gcd>1$，说明存在一个正整数$d>1$，满足d整除s内的所有元素

枚举$d=2 \to max_{a_i}$并统计答案

设$V=max_{a_i}$，则复杂度为$O(VlnV)$

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>using namespace std;const int maxn=100005;int n,tot,maxx=1;int a[maxn],fac[maxn];inline int read(){	int x=0,f=1;char ch=getchar();	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}	return x*f;}void record(int x){	for(int i=2;i*i<=x;i++)	{		if(x%i==0)		{			fac[i]++;			fac[x/i]++;		}		if(i*i==x)		fac[x/i]--;	}	fac[x]++;	return ;}int main(){	n=read(); 	for(int i=1;i<=n;i++)	{		a[i]=read();		record(a[i]);	}	sort(a+1,a+1+n);	for(int i=2;i<=a[n];i++)	maxx=max(maxx,fac[i]);	cout<<maxx<<endl;	return 0;}

CF776B Sherlock and his girlfriend

思路

注意到这是二分图，一边是质数，一边是合数

运用埃氏筛把合数都筛掉

然后质数和合数的颜色不同就可以了

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>using namespace std;int n;bool p[100005];int main(){	cin>>n;	p[0]=true,p[1]=true;	for(int i=2;i*i<=n+1;i++)	{		if(!p[i])		{			for(int j=i*2;j<=n+1;j+=i)			p[j]=true;		}	}	if(n<3)	cout<<1<<'\n';	else	cout<<2<<'\n';	for(int i=2;i<=n+1;i++)	cout<<(p[i]? 1:0)+1<<" ";	cout<<'\n';	return 0;}

P4139 上帝与集合的正确用法

思路

题目要求出的是$2^{2^{2^{2…}}} \space mod \space p$的值

根据扩展欧拉定理
$a^b\equiv \left\{\begin{aligned}a^{b \text{ mod }φ(p)+φ(p)}(b&>φ(p))\\a^b(b≤φ(p))\end{aligned}\right. \text{ (mod }p)$
可以通过一个函数来递归求

可是题目中让求的是无限层，并不是有限层，怎么办啊？
不要紧，在一层层的递归中，$p$一遍遍的被求其$φ$值，最终必定会降到$1$。原因很简单，因为：$φ(p)<p\space(p>1)$
而且降的很快，所以递归很快就会结束

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>using namespace std;const int maxn=1e7+5;int T,tot;int pri[1000005],phi[maxn];bool vis[maxn];inline int read(){	int x=0,f=1;char ch=getchar();	while (ch<'0'||ch>'9'){if (ch=='-') f=-1;ch=getchar();}	while (ch>='0'&&ch<='9'){x=x*10+ch-48;ch=getchar();}	return x*f;}int ksm(int a,int b,int p){	int ans=1%p;	for( ;b;b>>=1)	{		if(b&1)		ans=(long long)ans*a%p;		a=(long long)a*a%p; 	}	return ans;}int dfs(int x){	if(x==1)	return 0;	int n=phi[x];	return ksm(2,dfs(n)+n,x);}void init(){	for(int i=2;i<=maxn;i++)	{		if(!vis[i])		pri[++tot]=i,phi[i]=i-1;		for(int j=1;j<=tot&&pri[j]*i<=maxn;j++)		{			vis[pri[j]*i]=1;			if(i%pri[j])			phi[i*pri[j]]=phi[i]*phi[pri[j]];			else			{				phi[i*pri[j]]=phi[i]*pri[j];			}		}	}}int main(){	init();	T=read();	while(T--)		cout<<dfs(read())<<'\n';	return 0;}

一道例题

题目

求$[1,10^7]$内的所有素数，内存限制1MB

思路

吧$[1,10^7]$分成k段分别求解

对于区间$[l,r]$，枚举不大于$\sqrt{r}$的所有素数p，在$[l,r]$中筛去p的倍数

需要预处理$[1,\sqrt{n}]$的所有素数

时间复杂度$k\sqrt{n}+nlog^{log^n}$

空间复杂度$\sqrt{n}+n/k$

P2568 gcd

思路

线性筛出不大于$N$的所有素数$p$。问题就转化为求$(x,y)=p$的个数

设$x=x'p,y=y'p$那么有$(x',y')=1$且$1 \le x,y \le N/p$

转化为求$(x,y)=1$且$1 \le x,y \le n$的个数

答案为$2\sum_{i=1}^n\phi(i)-1$

线性筛筛出欧拉函数，预处理前缀和就可以了

然后对于每个小于等于$N$的素数处理累加到答案里就可以了

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>#define int long longusing namespace std;const int maxn=1e7+5;int pri[maxn],phi[maxn],s[maxn];bool vis[maxn];int n,tot;long long ans=0;void init(int x){	phi[1]=1;	for(int i=2;i<=x;i++)	{		if(!vis[i])		pri[++tot]=i,phi[i]=i-1;		for(int j=1;j<=tot&&pri[j]*i<=x;j++)		{			vis[pri[j]*i]=1;			if(i%pri[j])			phi[i*pri[j]]=phi[i]*phi[pri[j]];			else			{				phi[i*pri[j]]=phi[i]*pri[j];			}		}	}	for(int i=1;i<=x;i++)	s[i]=s[i-1]+phi[i];} signed main(){	cin>>n;	init(n);	for(int i=1;i<=tot;i++)	ans+=(2*s[n/pri[i]]-1);	cout<<ans<<'\n';	return 0;}

P2155 沙拉公主的困惑

思路

感谢@Siyuan

PS:越来越意识到开long long的重要性

答案是：
$\sum_{i=1}^{n!}[gcd(i,m!)=1]$
我们类比gcd

我们知道$n \ge m$，所以我们可以把$[1,n!]$分成若干段

准确地来说是 $\dfrac {n!} {m!}$段，每段的答案是一样的，这是由gcd的更相减损术得到的

然后我们就可以更换求和的上界
$\dfrac {n!} {m!}\sum_{i=1}^{m!}[gcd(i,m!)=1]$
右边的就是1到m！中与m互质的数，也就是
$\varphi(m!)$
我们知道,设$n =\prod p_i^{k_i}$,则$\varphi(n)=n \prod(1-\frac 1 {p_i})=\prod p_i^{k_i-1}*(p_i-1)$

所以我们设$m!=\prod_{i=1}^kp_i^{c_i}$,可以得到：
$\varphi(m!)=m! \prod_{i=1}^k \dfrac {p_i-1} {p_i}$
所以讲这个东西带入上面的式子，答案就是
$n!\prod_{i=1}^k \dfrac {p_i-1} {p_i}$
那个玩意儿我们可以用线性筛求

时间复杂度$O(N+T)$

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>#define int long longusing namespace std;const int maxn=1e7+5;int T,R;int tot,pri[maxn],fac[maxn],inv[maxn];int ans[maxn];bool vis[maxn];void init(){	fac[0]=fac[1]=1;	inv[0]=inv[1]=1;	ans[0]=ans[1]=1;	for(int i=2;i<=maxn-5;i++)	{		fac[i]=(long long)(fac[i-1]*i)%R;//算阶乘		inv[i]=(long long)((R-R/i)*inv[R%i])%R;//逆元 	}	//欧拉筛 	for(int i=2;i<=maxn-5;i++)	{   	 	if(!vis[i])    	    pri[++tot]=i;  		for(int j=1;j<=tot&&i*pri[j]<=maxn-5;j++)   	    {       	    vis[i*pri[j]]=1;            if(i%pri[j]==0)                break;        }    }    for(int i=2;i<=maxn-5;i++)    {    	ans[i]=ans[i-1];    	if(!vis[i])    	ans[i]=(long long)(ans[i]*(i-1)%R*inv[i]%R)%R;	}}signed main(){	cin>>T>>R;	init();	while(T--)	{		int n,m;		cin>>n>>m;		cout<<(long long)fac[n]*ans[m]%R<<'\n';	}	return 0;}

CF632D Longest Subsequence

思路

我们要选出尽可能多的数字，满足他们的最小公倍数不大于m

分析题意可以得到，如果一个数大于m的话那么它和其他数的最小公倍数一定大于m

所以先把大于m的数字筛掉

然后

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>using namespace std;const int maxn=1000005;int n,m;int a[maxn],ans[maxn];int cnt[maxn];bool vis[maxn];int main(){	std::ios::sync_with_stdio(false); 	cin>>n>>m;	for(int i=1;i<=n;i++)	{		cin>>a[i];		if(a[i]<=m)		cnt[a[i]]++;	}	for(int i=1;i<=n;i++)	{		if(a[i]<=m&&!vis[a[i]])		{			vis[a[i]]=true;			for(int j=1;j*a[i]<=m;j++)			ans[a[i]*j]+=cnt[a[i]];		}	}	int maxx=-9999999;	int lcm=1;	for(int i=1;i<=m;i++)	{		if(maxx<ans[i])		{			maxx=ans[i];			lcm=i;		}	}	cout<<lcm<<" "<<maxx<<'\n';	for(int i=1;i<=n;i++)	{		if(lcm%a[i]==0)		cout<<i<<" ";	}	cout<<'\n';	return 0;}

CF582A GCD Table

思路

为啥CF的题目就是这么妙呢？

是我不配了

观察得到三个结论

1.G中最大的数也一定是a中最大的数，因为$gcd(a,a)=a$，如果它是最大的话，也一定是最大的

2.G中次大的数也一定是a中次大的数

3.第三第四大的数可能是由最大和次大的GCD产生的；

所以算法就有这样的步骤

1.令p为G中最大的数，在G中删掉p，在a中加入p

2.对于a中的所有其他数，设为q，在G中删除两个$gcd(p,q)$

3.若G为空则结束，否则回到1

则时间复杂度为$O(n^2logG_{i,j})$

因为值域到$10^9$，所以要用map处理

#include <iostream>#include <cstdio>#include <algorithm>#include <cstring>#include <string>#include <map>using namespace std;const int maxn=505;int n,cnt,tot;int arr[maxn],a[maxn*maxn];map <int,int> m;int gcd(int a,int b){	return b? gcd(b,a%b):a;}int main(){	cin>>n;	for(int i=1;i<=n*n;i++)	{		int x;		cin>>x;		if(!m[x])		a[++cnt]=x;		m[x]++;	}	//从小到大排序，方便从大到小遍历	sort(a+1,a+1+cnt);	for(int i=cnt;i>=1&&tot<n; )	{		//如果前面没有，就一直减 		while(!m[a[i]])		i--;		arr[++tot]=a[i];		m[a[i]]--;		for(int j=1;j<tot;j++)		m[gcd(a[i],arr[j])]-=2;		//它和其他数的gcd都删掉了，所以要减两遍	}	for(int i=1;i<=tot;i++)	cout<<arr[i]<<" ";	return 0; }