数学简单复习

dzy posted @ 2014年3月22日 18:13 in 专题 with tags 数学 线性筛 , 1382 阅读

省选前不得不复(学)习一下数学了。

从xjoi上的一道题谈起:

 

你需要解决5个子问题:([tex]T[/tex]为数据组数)

(1)求[tex]ax \equiv 1 (\text{mod } p)[/tex]的最小正整数解[tex]x[/tex]

数据范围:[tex] 1 \leq a,p \leq 10^9 , 1 \leq T \leq 100000[/tex]

(2)求[tex]a^x \equiv 1 (\text{mod } p)[/tex]的最小正整数解[tex]x[/tex]

数据范围:[tex]1 \leq a,p \leq 10^9 , 1 \leq T \leq 2000[/tex] ,[tex]p[/tex]为素数且[tex]a[/tex]与[tex]p[/tex]互质。

(3)求[tex]\sum_{i=1}^n\sum_{j=1}^m\text{gcd}(i,j)[/tex]

数据范围:[tex]1 \leq n,m \leq 10^7, 1 \leq T \leq 1000[/tex]

(4)求[tex]\sum_{i=1}^n \left \lfloor \frac{n}{i} \right \rfloor[/tex]

数据范围:[tex]1 \leq n \leq 10^7, 1 \leq T \leq 100000[/tex]

(5)求[tex]c_{i}=\sum_{j=1}^{n-i}a_j b_{j+i}, 1 \leq i < n[/tex]

数据范围:[tex] n \leq 100000, 1 \leq a_i, b_i \leq 100[/tex]


(1)扩展欧几里得

非常显然,这就是个扩展欧几里得,记忆力不好就只好现推了。

当[tex]ab \neq 0[/tex]时,一定存在整数对[tex]x,y[/tex]使得[tex]ax+by \equiv \text{gcd}(a,b)[/tex]

设[tex] a>b[/tex]

[tex]b=0[/tex]时,[tex]\text{gcd}(a,b)=a[/tex],此时[tex]x=1,y=0[/tex]

[tex]b \neq 0[/tex]时,设

[tex]ax_{1}+by_{1}=\text{gcd}(a,b)

[tex]bx_{2}+(a \text{ mod } b) y_{2} = \text{gcd}(b,a \text{ mod } b)

显然有[tex]\text{gcd}(a,b)=\text{gcd}(b,a \text{ mod } b)[/tex]

那么就有[tex]ax_{1}+by_{1}=bx_{2}+(a \text{ mod } b) y_{2}[/tex]

接着把[tex] (a \text{ mod } b)[/tex]用[tex](a- \left \lfloor \frac{a}{b} \right \rfloor b)[/tex]替换掉。

可以得到[tex]ax_1+by_1=ay_2+b(x_2-  \left \lfloor \frac{a}{b} \right \rfloor  y_2)[/tex]

解为[tex]x_1=y_2,y_1=x_2- \left \lfloor \frac{a}{b} \right \rfloor  y_2[/tex]

整个过程递归进行,时间复杂度[tex]\text{O} (T\text{log}a)[/tex]


(2)离散对数(小步大步算法)

orz jcvb 非常好懂 —— 传送门

(为了完整性我粘过来=。=)

 
[tex]a^x \equiv b (\text{mod} p)[/tex]求最小的非负整数x。默认[tex]a \neq 0,p\geq 2[/tex]。
  • bzoj3239模为质数(裸的BSGS)
若[tex]p|a[/tex]。[tex]b \equiv 0[/tex]时,[tex]x=1[/tex];否则x无解。
否则a,p互质,由费马小定理,只需考虑[tex]x=0,1,\dots,p-2[/tex]。
取一个m,令[tex]x=mi-j[/tex],[tex]i=1,2,\dots,m[/tex],[tex]j=1,2,\dots,m[/tex]。此时[tex]x=0,1,\dots,m^2-1[/tex],所以只要取[tex]m^2\geq p-1[/tex]即可。
则[tex]a^{mi-j} \equiv b(\text{mod}p)[/tex]
等价于[tex]a^{mi} \equiv b\cdot a^j(\text{mod}p)[/tex]
等号两边分别遍历i和j,用hash表检查是否出现重复值,并保留最小解即可。
  • bzoj2995模可能为合数
分解模[tex]p=\prod_{i=1}^k {p_i}^{d_i}[/tex],等价转换为k个形如[tex]a^x \equiv b(\text{mod}p^d)[/tex]的方程。若其中任意一个无解,则原方程无解。
①[tex]p \nmid a[/tex],则可以使用上述BSGS解出最小非负整数解[tex]x_0[/tex]。
再求[tex]a^x \equiv 1(\text{mod}p^d)[/tex]的最小正整数解K(即a对模p^d的阶),可以用BSGS,也可以枚举[tex]\varphi(p^d)=p^d-p^{d-1}[/tex]的所有约数进行检查。
则所有形如[tex]x\equiv x_0(\text{mod}K)[/tex]的非负整数x均是此方程的解。
(当[tex]a\equiv 1(\text{mod}p^d)[/tex]时此方法仍然有效,其中求得的K=1)
②[tex]p|a[/tex],且[tex]b\equiv 0 (\text{mod}p^d)[/tex]。
由于a中含有p的因子,那么在x充分大的时候一定能有[tex]a^x\equiv 0\equiv b(\text{mod}p^d[/tex]。
令[tex]a=p^qa'[/tex],[tex]q\geq 1,p\nmid a'[/tex],则[tex]x \geq x_0=\left \lceil d/q \right \rceil[/tex]均为此方程的解。
③[tex]p|a[/tex],且[tex]b \not \equiv 0(\text{mod}p^d)[/tex]。
由上讨论,可知此时x不会超过[tex]d/q[/tex],而这是一个很小的范围(在32以内)。所以若这种情况出现,只需对原方程暴力检验32以内的x后即可跳出。
假如不出现情况③,把①中得到的所有结果合并,并从中取满足②下界的最小x即为答案。
 
 
针对这道题p为质数,可得x|p-1,直接枚举约数可以过。

(3)(4)线性筛

继续orz jcvb

两个重要性质灵活的用就方便许多了。
 
1:[tex]\sum_{d|n}{\mu(d)}=[n==1][/tex],即[tex]1*\mu=\epsilon[/tex]。(可用二项式定理证明)
2:[tex]\sum_{d|n}{\varphi(d)}=n[/tex],即[tex]1*\varphi=\text{id}[/tex]。(n是质数时显然成立,再由积性得证)

(3)相同一段一起算。

(4)可以转化成约数和的前缀和,才可以满分。


(5)FFT

反转第二个数组,发现求的就是两个数组的卷积。上FFT即可。


无聊不如贴份代码好了233

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;

typedef long long ll;
const double pi=3.1415926535897932384626;
struct problem_1{
	ll exgcd(ll &x,ll &y,ll a,ll b){
		if(!b){
			x=1;
			y=0;
			return a;
		}
		ll xx,yy,d=exgcd(xx,yy,b,a%b);
		x=yy;
		y=xx-(a/b)*yy;
		return d;
	}
	ll equ(ll a,ll b,ll c){
		ll x,y,d=exgcd(x,y,a,c);
		if(b%d)	return -1;
		ll e=x*(b/d)%c;
		while(e<0)	e+=c/d;
		return e;
	}
	void solve(){
		int tc;
		scanf("%d",&tc);
		ll a,p,x,y,d;
		while(tc--){
			scanf("%lld%lld",&a,&p);
			printf("%lld\n",equ(a,1,p));
		}
	}
}p_1;

struct problem_2{
	int pow(int a,int b,int c){
		int an=1;
		while(b){
			if(b&1)	an=1ll*an*a%c;
			b>>=1;
			a=1ll*a*a%c;
		}
		return an;
	}
	int getans(int a,int p){
		int t=p-1,ans=p;
		for(int i=1;i*i<=t;i++){
			if(t%i==0){
				if(pow(a,i,p)==1)	ans=min(ans,i);
				if(pow(a,t/i,p)==1)	ans=min(ans,t/i);
			}
		}
		return ans;
	}
	void solve(){
		int tc,a,p;
		scanf("%d",&tc);
		while(tc--){
			scanf("%d%d",&a,&p);
			printf("%d\n",getans(a,p));
		}
	}
}p_2;

int flag[10000010],g[10000010],prime[2000000],pcnt;
long long phi[10000010],f[10000010];
struct problem_3{
	void sieve(int n){
		memset(flag,0,sizeof(flag));pcnt=0;
		for(int i=2;i<=n;i++){
			if(!flag[i])	prime[++pcnt]=i,phi[i]=i-1;
			for(int j=1;j<=pcnt && i*prime[j]<=n;j++){
				flag[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);
				}
			}
		}
		phi[1]=1;
		for(int i=2;i<=n;i++)	phi[i]+=phi[i-1];
	}
	void solve(){
		sieve(10000000);
		int tc,n,m,n1;
		ll ans;
		scanf("%d",&tc);
		while(tc--){
			scanf("%d%d",&n,&m);
			if(n>m)	swap(n,m);
			ans=0;
			for(int i=1;i<=n;i=n1+1){
				n1=min(n/(n/i),m/(m/i));
				ans+=1ll*(n/i)*(m/i)*(phi[n1]-phi[i-1]);
			}
			printf("%lld\n",ans);
		}
	}
}p_3;

struct problem_4{
	void sieve(int n){
		for(int i=2;i<=n;i++){
			if(!flag[i])	prime[++pcnt]=i,g[i]=1,f[i]=2;
			for(int j=1;j<=pcnt && prime[j]*i<=n;j++){
				flag[i*prime[j]]=1;
				if(i%prime[j]==0){
					g[i*prime[j]]=g[i]+1;
					f[i*prime[j]]=f[i]/(g[i]+1)*(g[i]+2);
					break;
				}else{
					f[i*prime[j]]=f[i]*2;
					g[i*prime[j]]=1;
				}
			}
		}
		f[1]=1;
		for(int i=2;i<=n;i++)	f[i]+=f[i-1];
	}
	void solve(){
		sieve(10000000);
		int tc,n;
		scanf("%d",&tc);
		ll ans;
		while(tc--){
			scanf("%d",&n);
			printf("%lld\n",f[n]);
		}
	}
}p_4;

struct problem_5{
	struct cpx{
		double a,b;
		cpx operator + (const cpx&o)const{	return (cpx){a+o.a,b+o.b};}
		cpx operator - (const cpx&o)const{	return (cpx){a-o.a,b-o.b};}
		cpx operator * (const cpx&o)const{	return (cpx){a*o.a-b*o.b,b*o.a+a*o.b};}
	}a[400010],b[400010];
	int an[400010],len,tmp[100];
	int rev(int x){
		tmp[0]=0;
		for(;x;x>>=1)	tmp[++tmp[0]]=x&1;
		int t=0;
		for(int i=1;i<=tmp[0];i++)	if(tmp[i])	t+=1<<(len-i);
		return t;
	}
	void fft(cpx *A,int n,int fl=1){
		for(int i=0;i<n;i++){
			int t=rev(i);
			if(i<t)	swap(A[i],A[t]);
		}
		for(int m=2;m<=n;m<<=1){
			cpx w=(cpx){cos(fl*2*pi/(double)m),sin(fl*2*pi/(double)m)};
			for(int k=0;k<n;k+=m){
				cpx cur=(cpx){1,0};
				for(int j=k;j<k+(m>>1);j++,cur=cur*w){
					cpx t=cur*A[j+(m>>1)],u=A[j];
					A[j]=u+t;
					A[j+(m>>1)]=u-t;
				}
			}
		}
	}
	void solve(){
		int n;
		scanf("%d",&n);
		memset(a,0,sizeof(a));memset(b,0,sizeof(b));
		for(int i=0;i<n;i++)	scanf("%lf",&a[i].a);
		for(int i=0;i<n;i++)	scanf("%lf",&b[n-i-1].a);
		len=0;
		while((1<<len)<2*n)	len++;
		fft(a,(1<<len));
		fft(b,(1<<len));
		for(int i=0;i<(1<<len);i++)	a[i]=a[i]*b[i];
		fft(a,(1<<len),-1);
		for(int i=0;i<(1<<len);i++)	an[i]=(int)(a[i].a/(double)(1<<len)+0.5);
		for(int i=n-2;~i;i--)	printf("%d\n",an[i]);
	}
}p_5;
int main(){
	int testid;
	scanf("%d",&testid);
	if(testid>=1 && testid<=2)	p_1.solve();
	else	if(testid>=3 && testid<=6)	p_2.solve();
	else	if(testid>=7 && testid<=10)	p_3.solve();
	else	if(testid>=11 && testid<=14)	p_4.solve();
	else	p_5.solve();
	return 0;
}

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter