DZY 's BLOG
Hello World!
dzy493941464
Music
标签云
Orz
搜索
计数器
最新评论
功能
随机文章
热门文章
数学简单复习
省选前不得不复(学)习一下数学了。
从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）离散对数（小步大步算法）
（为了完整性我粘过来=。=）
- bzoj3239模为质数(裸的BSGS)
- bzoj2995模可能为合数
（3）（4）线性筛
继续orz jcvb
（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;
}
评论 (0)