bzoj 4454 C Language Practice最大公約数
2534 ワード
最大公約数のO(N)前処理O(1)を求める.
まずm=N^0.5とすると,i,j<=mであり,状態数と時間がO(m*m)=O(N)であるすべてのgcd(i,j)を記憶化探索の形で得ることができる.
では、Nを超えない2つの数x,yのgcdを求めることを考えます.私たちは必ずxを3つの数a,b,cに分解することができて、すべての数はすべて<=mを満たすか、あるいは質数で、簡単な証明は以下の通りです:
あるxに関するaが条件を満たさないと仮定すると、aが合数であり、a>mであることは明らかである.では、aの1つの分解方式をa=uv(u>vとしてもよい)と仮定すると、a>mでabc=xでは、a、b、c、yに対してそれぞれgcdを求めてから並べ替えることを考えます.aに対する操作を仮定する.前処理によりaが素数であるか否かを知ることができ、素数であればy mod a=0があるか否かを判断し、満足すればy/=a,ans*=aとし、そうでなければ必ずa<=mがあると判断し、gcd(m,n)=gcd(n,m mod n)からgcd(y,a)=gcd(a,y mod a)を得ることができ、明らかにaとy mod aともに<=mであれば、この部分の前処理はすでに得られている.
このようにO(N)前処理O(1)を行うことができる.この問題カードのメモリに注意して、正確にm=N^0.5を取ることしかできなくて、実践の中でmを少し大きくすることができます.
MACコードは以下の通りである.
by lych
2016.3.30
まずm=N^0.5とすると,i,j<=mであり,状態数と時間がO(m*m)=O(N)であるすべてのgcd(i,j)を記憶化探索の形で得ることができる.
では、Nを超えない2つの数x,yのgcdを求めることを考えます.私たちは必ずxを3つの数a,b,cに分解することができて、すべての数はすべて<=mを満たすか、あるいは質数で、簡単な証明は以下の通りです:
あるxに関するaが条件を満たさないと仮定すると、aが合数であり、a>mであることは明らかである.では、aの1つの分解方式をa=uv(u>vとしてもよい)と仮定すると、a>mでabc=x
このようにO(N)前処理O(1)を行うことができる.この問題カードのメモリに注意して、正確にm=N^0.5を取ることしかできなくて、実践の中でmを少し大きくすることができます.
MACコードは以下の通りである.
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,m,cnt,a[2005],b[2005],f[1000005][3],g[1005][1005],p[1000005],c[100005];
int read(){
int x=0; char ch=getchar();
while (ch<'0' || ch>'9') ch=getchar();
while (ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
return x;
}
int get_g(int x,int y){
return (x && y)?g[y][x%y]:x|y;
}
int gcd(int x,int y){
if (x<=1000 && y<=1000) return g[x][y];
if (!x || !y) return x|y;
int d=1,i;
for (i=0; i<3; i++) if (f[x][i]>1){
int t=f[x][i];
if (p[t]==t){
if (!(y%t)){
y/=t; d*=t;
}
} else{
int z=g[t][y%t];
y/=z; d*=z;
}
}
return d;
}
int main(){
int i,j,cas=read();
for (i=0; i<=1000; i++)
for (j=0; j<=i; j++) g[i][j]=g[j][i]=get_g(i,j);
p[1]=1;
for (i=2; i<=1000000; i++){
if (!p[i]){
p[i]=i; c[++cnt]=i;
}
for (j=1; j<=cnt && i*c[j]<=1000000; j++){
p[i*c[j]]=c[j];
if (!(i%c[j])) break;
}
}
f[1][0]=f[1][1]=f[1][2]=1;
for (i=2; i<=1000000; i++){
memcpy(f[i],f[i/p[i]],sizeof(f[i]));
if (f[i][0]*p[i]<=1000) f[i][0]*=p[i];
else if (f[i][1]*p[i]<=1000) f[i][1]*=p[i];
else f[i][2]*=p[i];
}
while (cas--){
m=read(); n=read();
for (i=0; i<m; i++) a[i]=read();
for (i=0; i<n; i++) b[i]=read();
unsigned int ans=0;
for (i=0; i<m; i++) for (j=0; j<n; j++){
ans+=gcd(a[i],b[j])^i^j;
}
printf("%u
",ans);
}
return 0;
}
by lych
2016.3.30