【笔记】基础数论

来自\(\texttt{SharpnessV}\)的省选复习计划中的基础数论


CF1355F Guess Divisors Count

交互题,给定\(X\le10^{9}\),每次可以询问\(\gcd (X,Q_i)\),\(Q_i\le 10^{18}\),并在 $22 $ 次询问内求出 \(X\) 的约数个数,允许有一倍的误差。

首先 \(\ge 10^3\) 的质数最多\(2\)个,如果存在\(\ge 10^3\)的质数,则约数个数最少\(\times 2\),最多\(\times 4\)。不考虑\(\ge 10^3\)的约数能够满足一倍的误差。

考虑\(\le 10^3\)以内的约数,总数不多,先询问出有哪些质因子,然后询问质因子的次幂。

虽然这个方法可以在很少次数内完成,但是特殊构造的数据能然会超过\(22\)次。

首先如果我们找到了一个质因子的次幂,上界\(10^3\)会对应下移。比如找到一个 \(2\),则\(800\)以上的质数可以忽略,因为\(800^3\ge5\times 10^8\)。

如果一直没有找到质数,我们忽略\(\ge 100\) 的质数,因为\(100^5 \ge 10^9\),所以最多也就 \(16\) 个约数,最少 \(2\) 个约数。

Code


P1072 [NOIP2009 提高组] Hankson 的趣味题

求\(\gcd (a_0,x)=a_1\ \ \land\ \ \rm lcm(b_0,x)=b_1\) 的 \(x\) 的个数。

$ x $ 一定是 \(b_1\) 的约数,我们枚举 \(b_1\) 的约数并\(\rm check\)即可,因为一个数的约数个数不会很多,所以复杂度是对的。

时间复杂度\(\rm O(N\sqrt{b}+N\sigma(b)\log b)\)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll gcd(ll a,ll b){
	if(!b) return a;
    else return gcd(b,a%b);
}
inline ll lcm(ll a,ll b){
	return a*b/(gcd(a,b));
}
int main()
{
	int n;ll ans;scanf("%d",&n);ll a0,a1,b0,b1;
	for(int i=1;i<=n;i++){
		ans=0;
		scanf("%lld%lld%lld%lld",&a0,&a1,&b0,&b1);
    	for(int j=1;j*j<=b1;j++)
		  if(b1%j==0){
			if(gcd((ll)j,a0)==a1&&lcm((ll)j,b0)==b1)ans++;
			if(b1/j!=j)
			  if(gcd(b1/j,a0)==a1&&lcm(b1/j,b0)==b1)ans++;
		}
		printf("%lld\n",ans);
	}
	return 0;
}

P2152 [SDOI2009]SuperGCD

高精度取模非常不可做,考虑辗转相减法。

\(\forall a>b\ \ ,\ \ \rm gcd(a,b)=gcd(b,a-b)\) 。

但辗转相减会被卡到\(\rm O(N)\),我们需要二进制优化。

显然 \(\forall\ 2|a,b\ \ ,\ \ \rm gcd(a,b)=2gcd(\dfrac{a}{2},\dfrac{b}{2})\) 。

并且 \(\forall\ 2|a,2\nmid b\ \ ,\ \ \rm gcd(a,b)=gcd(\dfrac{a}{2},b)\)。

这样就能保证复杂度为\(\rm O(\log N)\)。


P2158 [SDOI2008]仪仗队

求\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}[\gcd (i,j)=1]\) 。

这里 \(n\) 很小,直接用\(\varphi\)的定义即可,\(ans=\sum\limits_{i=1}^{n}\varphi(i)\) 。

求\(\varphi\),可以线性筛,也可以质因数分解。

#include<bits/stdc++.h>
using namespace std;
int oula(int x){
	int ans=x;
	for(int i=2;i*i<=x;i++){
		if(x%i==0){
		  ans=ans/i*(i-1);
		  while(x%i==0)x/=i;
	    }
	}
	if(x>1)ans=ans/x*(x-1);
	return ans;
}
int main()
{
	int n,ans=0;scanf("%d",&n);n--;
	for(int i=2;i<=n;i++){
	    ans+=oula(i)*2;
	}
	if(n)ans+=3;
	printf("%d",ans);
	return 0;
}

P2398 GCD SUM

求\(\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{n}\gcd (i,j)\) 。

显然约数有 \(d\) 的 \((i,j)\) 对数为 \(\left\lfloor\dfrac{n}{d}\right\rfloor^2\),容斥求出最大公约数为 \(d\) 的对数。

时间复杂度为\(\sum\limits_{i=1}^{n}\frac{n}{i}=\rm O(N\log N)\)。

当然也可以反演 \(\varphi *1=\rm Id\) 。

#include<cstdio>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
long long n,ans,f[100010];
int main(){
    scanf("%lld",&n);
    pre(i,n,1){
        f[i]=n/i*(n/i);
        for(int j=i*2;j<=n;j+=i)f[i]-=f[j];
        ans+=f[i]*i;
    }
    printf("%lld",ans);
	return 0;
}

P2568 GCD

求\(\gcd(x,y)=p\)的对数,我们可以求\(\gcd(x_0,y_0)=1\)的对数,然后枚举 \(p\) 令\(x=x_0\times p,y=y_0\times p\)。

互质数对恰好为\(\sum \varphi\),线性筛一下即可。


P4139 上帝与集合的正确用法

费马小定理

\[\forall a\in P\ ,\ a^p\equiv a\pmod{p} \]

欧拉定理

\[\forall a\perp p\ ,\ a^{\varphi(p)}\equiv 1\pmod{p} \]

扩展欧拉定理

\[a^c\equiv\begin{cases}a^c&c\leq\varphi(p)\\a^{c\bmod \varphi(p)+\varphi(p)}&c>\varphi(p)\end{cases} \]

这道题令\(k=2^{2^{\cdots}}\),有\(k\equiv 2^k\pmod{p}\)。

所以\(k=2^{k\bmod \varphi(p)+\varphi(p)} \bmod p\)。

递归下去即可,边界为 \(p=1\) 。


P4549 【模板】裴蜀定理

\(ax+by=c\)有整数解的充要条件是 \(\gcd (a,b)\mid c\) 。

所以裴蜀定理就是\(n\)元整数方程有解的冲要条件是所有系数的最大公约数整除\(c\)。

#include<bits/stdc++.h>
using namespace std;
int n,a[25],ans;
int gcd(int x,int y){
	return y?gcd(y,x%y):x;
}
int main()
{
	scanf("%d",&n);
	scanf("%d",&ans);
	for(int i=1;i<n;i++)scanf("%d",&a[i]),ans=gcd(ans,a[i]<0?-a[i]:a[i]);
	printf("%d\n",ans);
	return 0;
}

P2613 【模板】有理数取余

一般用费马小定理求逆元,模数不为质数用扩展欧几里得算法。

#include<bits/stdc++.h>
#define P 19260817
using namespace std;
inline int read()
{
	int sum=0;char ch=getchar();
	while(ch>'9'||ch<'0')ch=getchar();
	while(ch<='9'&&ch>='0')sum=(sum*10+ch-'0')%P,ch=getchar();
	return sum;
}
long long Pow(long long x,int y){
	long long mul=1;
	for(;y;y>>=1,x=(x*x)%P)
		if(y&1)mul=(mul*x)%P;
	return mul;
}
int main()
{
	int a=read();
	int b=read();
	if(!b)puts("Angry!");
	else{
		//cout<<a<<" "<<b<<endl;
		printf("%lld\n",(long long)Pow(b,P-2)*a%P);
	}
	return 0;
	
}

P3811 【模板】乘法逆元

线性求逆元。

令 \(ki+r=p\) 。

\[ki+r\equiv0 \]

\[kr^{-1}+i^{-1}\equiv0 \]

线性递推即可。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define N 3000005
int inv[N],n,p;
int main(){
	scanf("%d%d",&n,&p);
	inv[1]=1;
	rep(i,2,n)inv[i]=-1LL*(1LL*inv[p%i]*(p/i))%p;
	rep(i,1,n)printf("%d\n",inv[i]<0?p+inv[i]:inv[i]);
	return 0;
}

P5431 【模板】乘法逆元2

离线,将所有要求逆元的数乘起来求逆元,再乘上前缀积与后缀积即可。

#include<bits/stdc++.h>
using namespace std;
int n,p,k;
char buf[1<<23],*p1=buf,*p2=buf,obuf[1<<23],*O=obuf;
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
inline int read(){
    int x=0;char ch=getchar();
    while(!isdigit(ch))ch=getchar();
    while(isdigit(ch))x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return x;
}
void print(int x) {
    if(x>9) print(x/10);
    *O++=x%10+'0';
}
int a[5000005],sum=1,mul[5000005],mul_[5000005];
int Pow(long long x,int y){
	long long now=1;
	for(;y;y>>=1,x=x*x%p)
	  if(y&1)now=now*x%p;
	return now;
}
int main()
{
	n=read();p=read();k=read();
	for(register int i=1;i<=n;i++)
	  a[i]=read(),sum=(long long)sum*a[i]%p,mul[i]=sum;
	mul_[n]=a[n];
	for(register int i=n-1;i;i--)
	  mul_[i]=(long long)mul_[i+1]*a[i]%p;
	sum=Pow(sum,p-2);
	mul[0]=mul_[n+1]=1;int m=k,ans=0;
	for(register int i=1;i<=n;i++)
	  ans=(ans+(long long)sum*mul[i-1]%p*m%p*mul_[i+1]%p)%p,m=(long long)m*k%p;
	print(ans);
	fwrite(obuf,O-obuf,1,stdout);
	return 0;
}

P3951 [NOIP2017 提高组] 小凯的疑惑

答案为\(\rm ab-a-b\),证明可以反证法,直接推导难度较高,可以直接打表。

#include<cstdio>
long long int a, b;
int main()
{
    scanf("%lld%lld",&a,&b);
    printf("%lld",a*b-a-b);
    return 0;
}

P1082 [NOIP2012 提高组] 同余方程

扩展欧几里得算法,用于求解形如 \(ax+by=\gcd(a,b)\) 的不定方程。

\[ax\equiv 1\pmod{b} \]

等价于

\[ax+by=1 \]

所以有解的充要条件是\(a\perp b\) 。然后套用扩欧即可。

#include<bits/stdc++.h>
void exgcd(int a,int b,int &x,int &y){
	if(b==0)x=1,y=0;
	else{
		int xx,yy;
		exgcd(b,a%b,xx,yy);
		x=yy;y=xx-a/b*yy;
	}
}
int a,b;
int main(){
	scanf("%d%d",&a,&b);
	int x,y;exgcd(a,b,x,y);
	printf("%d\n",(x%b+b)%b);
	return 0;
}

P1516 青蛙的约会

写出方程:\((m-n)d\equiv x-y \pmod{L}\)。

线性同余方程,直接\(\rm exgcd\)即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int exgcd(int a,int b,int &x,int &y){
	if(!b){
		x=1;y=0;return a;
	}
	int x0,y0,c;
	c=exgcd(b,a%b,x0,y0);
	x=y0;y=x0-(a/b)*y0;
	return c;
}
signed main()
{
	int x,y,m,n,l;
	scanf("%lld%lld%lld%lld%lld",&x,&y,&m,&n,&l);
	int p,t,c,a,b;
	b=(n-m);a=(x-y);
	if(b<0)b=-b,a=-a;
	c=exgcd(b,l,t,p);
	if(a%c)printf("Impossible\n");
	else printf("%lld\n",((t*(a/c))%(l/c)+(l/c))%(l/c));
	return 0;
}

P3846 [TJOI2007] 可爱的质数/【模板】BSGS

\(\rm BSGS\)算法,根号分治的一种应用。

我们令\(t=\left\lfloor\sqrt{P}\right\rfloor+1\),预处理\(a^{t},a^{2t},\cdots,a^{t^2}\)和\(a^{0},a^1,\cdots,a^{t-1}\)次幂,开一个哈希表维护即可。

\(b\times a^x\equiv a^y\),则\(a^{y-x}\equiv x\)。时间复杂度\(\rm O(\sqrt N)\),如果用\(\rm map\)是带\(\log\)的。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 100005
#define int long long
using namespace std;
int p,b,n;
map<int,int>h;
void BSGS(){
	h.clear();
	int a=1,t=sqrt(p*2)+1;
	rep(i,0,t-1){
		h[a*n%p]=i;
		a=a*b%p;
	}
	int k=a;
	rep(i,1,t){
		if(h.count(a)){
			printf("%lld\n",t*i-h[a]);
			return;
		}
		a=a*k%p;
	}
	printf("no solution\n");
}
signed main(){
	scanf("%lld%lld%lld",&b,&p,&n);
	while(p&&b&&n){
		BSGS();
		scanf("%lld%lld%lld",&b,&p,&n);
	}
	return 0;
}

P4195 【模板】扩展BSGS

模数不为质数,递归处理,需要用\(\rm exgcd\)求逆元。

如果遇到模数不是质数的题喷出题人就完事。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define int long long
using namespace std;
int gcd(int x,int y){return y?gcd(y,x%y):x;}
void exgcd(int a,int b,int &x,int &y){
	if(!b){x=1;y=0;return;}
	int xx,yy;exgcd(b,a%b,xx,yy);
	x=yy;y=xx-(a/b)*yy;
}
int inv(int a,int p){
	int xx,yy;
	exgcd(a,p,xx,yy);
	return (xx%p+p)%p;
}
map<int,int>h;
int BSGS(int a,int b,int p){
	h.clear();a%=p;b%=p;
	int t=sqrt(p)+1,k=1;
	rep(i,0,t-1){
		h[k*b%p]=i;
		k=k*a%p;
	}
	a=k;k=1;
	rep(i,0,t){
		if(h.count(k)){
			int j=h[k];
			if(i*t-j>=0)return i*t-j;
		}
		k=k*a%p;
	}
	return -1;
}
void exBSGS(int a,int b,int p,int mul,int sum){
	if(b==1||p==1){printf("%lld\n",sum);return;}
	int g=gcd(a,p);
	if(b%g){puts("No Solution");return ;}
	if(g==1){
		int ans=BSGS(a,b*inv(mul,p)%p,p);
		if(~ans)printf("%lld\n",ans+sum);
		else puts("No Solution");
		return;
	}
	exBSGS(a,b/g,p/g,(a/g*mul)%p,sum+1);
}
signed main(){
	int a,b,p;scanf("%lld%lld%lld",&a,&p,&b);
	while(a&&b&&p){
		exBSGS(a,b,p,1,0);
		scanf("%lld%lld%lld",&a,&p,&b);
	}
	return 0;
}                      

P5491 【模板】二次剩余

没啥用的模板,看看就行。


P2485 [SDOI2011]计算器

三合一的题目。

第一问直接快速幂。

第二问是线性同余方程,直接\(\rm exgcd\)即可。

第三问直接\(\rm BSGS\)即可。

正好复习一下板子。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define pre(i,a,b) for(int i=a;i>=b;i--)
#define N 100005
#define int long long
using namespace std;
int Pow(int x,int y,int p){
	int now=1;
	for(;y;y>>=1,x=x*x%p)if(y&1)now=now*x%p;
	return now;
}
int gcd(int x,int y){return y?gcd(y,x%y):x;}
void exgcd(int a,int b,int &x,int &y){
	if(!b){x=1;y=0;return ;}
	int xx,yy;exgcd(b,a%b,xx,yy);
	x=yy;y=xx-(a/b)*yy;
}
map<int,int>h;
void solve(int a,int b,int p){
	h.clear();
	int t=sqrt(p)+1,k=1;
	rep(i,0,t-1){
		h[k*b%p]=i;
		k=(k*a)%p;
	}
	a=k;k=1;
	if(a%p==0&&b){puts("Orz, I cannot find x!");return;}
	rep(i,0,t){
		if(h.count(k)){
			int j=h[k];
			if(i*t-j>=0){
				printf("%lld\n",i*t-j);
				return;
			}
		}
		k=(k*a)%p;
	}
	puts("Orz, I cannot find x!");
}
signed main(){
	int T,op;
	scanf("%lld%lld",&T,&op);
	if(op==1){
		int x,y,z;
		while(T--){
			scanf("%lld%lld%lld",&x,&y,&z);
			printf("%lld\n",Pow(x,y,z));
		}
	}
	else if(op==2){
		int y,z,p,x,X;
		while(T--){
			scanf("%lld%lld%lld",&y,&z,&p);
			int g=gcd(y,p);
			if(z%g){puts("Orz, I cannot find x!");continue;}
			exgcd(y,p,x,X);
			x=((z/g*x)%p+p)%p;printf("%lld\n",x);
		}
	}
	else{
		int a,b,p;
		while(T--)scanf("%lld%lld%lld",&a,&b,&p),solve(a,b,p);
	}
	return 0;
}

P3306 [SDOI2013] 随机数生成器

基础数列题。

给定递推式\(x_i=ax_{i-1}+b\),这就是一阶递推数列,一波推导得到它的通项公式。

\[x_n=a^{n-1}(x_1+\dfrac{b}{a-1})-\dfrac{b}{a-1} \]

解方程

\[x_n=t \]

显然只有\(n\)未知,直接\(\rm BSGS\)即可。

众所周知等比数列\(a=1\)需要特判,\(a=0\)也要特判。

Code


P4884 多少个1?

同样是数列,我们设数列第 \(n\) 项是 \(n\) 个 \(1\)。有递推式

\[a_n=10a_{n-1}+1 \]

把这个数列的递推公式解出来就是

\[a_n=\dfrac{10^n-1}{9} \]

现在解\(a_n\equiv K \pmod m\)。直接\(\rm BSGS\)即可。

Code


P4861 按钮

扩展\(\rm BSGS\),出题人应该爬。

Code


P4454 [CQOI2018]破解D-H协议

很新的一道题,看来\(\rm BSGS\)还没有成为时代的眼泪。

给定\(g^a\)和\(g^b\),求\(g^{ab}\)。

直接\(\rm BSGS\)解出\(a\),然后快速幂即可。

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define int long long 
using namespace std;
int g,P;
int Pow(int x,int y){
	int now=1;
	for(;y;y>>=1,x=x*x%P)if(y&1)now=now*x%P;
	return now;
}
map<int,int>h;
int BSGS(int x){
	h.clear();
	int a=1,t=sqrt(P)+1;
	rep(i,0,t-1)h[a*x%P]=i,a=a*g%P;
	int k=a;
	rep(i,1,t)if(h.count(k))return i*t-h[k];else k=k*a%P;
	return -1;
}
signed main(){
	scanf("%lld%lld",&g,&P);
	int n;scanf("%lld",&n);
	while(n--){
		int a,b;scanf("%lld%lld",&a,&b);
		int x=BSGS(a);
		printf("%lld\n",Pow(b,x));
	}
	return 0;
}
上一篇:生活大爆炸第五季 那些精妙的台词翻译


下一篇:【YBTOJ】【UVA10140】Prime Distance