「BZOJ2820」YY的GCD
Description
神犇YY虐完数论后给傻×kAc出了一题
给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对
kAc这种傻×必然不会了，于是向你来请教……
多组输入
Input
第一行一个整数T 表述数据组数
接下来T行，每行两个正整数，表示N, M
Output
T行，每行一个整数表示第i组数据的结果
Sample Input
2
10 10
100 100
10 10
100 100
Sample Output
30
2791
2791
HINT
T = 10000
N, M <= 10000000
Source
假定n<m
\[\sum_{isprime(p)}\sum_{a=1}^n\sum_{b=1}^mgcd(a,b)==p\]
\[\sum_{isprime(p)}\sum_{a=1}^{\left \lfloor \frac{n}{p} \right \rfloor}\sum_{b=1}^{\left \lfloor \frac{m}{p} \right \rfloor}gcd(a,b)==1\]
\[\sum_{isprime(p)}\sum_{a=1}^n\sum_{b=1}^mgcd(a,b)==p\]
\[\sum_{isprime(p)}\sum_{a=1}^{\left \lfloor \frac{n}{p} \right \rfloor}\sum_{b=1}^{\left \lfloor \frac{m}{p} \right \rfloor}gcd(a,b)==1\]
\[\sum_{isprime(p)}\sum_{a=1}^{\left \lfloor \frac{n}{p} \right \rfloor}\sum_{b=1}^{\left \lfloor \frac{m}{p} \right \rfloor}\sum_{d|gcd(a,b)}\mu(d)\]
\[\sum_{isprime(p)}\sum_{a=1}^{\left \lfloor \frac{n}{p} \right \rfloor}\sum_{b=1}^{\left \lfloor \frac{m}{p} \right \rfloor}\sum_{d|a \land d|b}\mu(d)\]
\[\sum_{isprime(p)}\sum_{d=1}^{\left \lfloor \frac{n}{p} \right \rfloor}\mu(d){\left \lfloor \frac{n}{pd} \right \rfloor}{\left \lfloor \frac{m}{pd} \right \rfloor}\]
将pd设为k
\[\sum_{k=1}^{n}\sum_{isprime(p) \land p|k}\mu(\frac{k}{p}){\left \lfloor \frac{n}{k} \right \rfloor}{\left \lfloor \frac{m}{k} \right \rfloor}\]
\[\sum_{k=1}^{n}F(k){\left \lfloor \frac{n}{k} \right \rfloor}{\left \lfloor \frac{m}{k} \right \rfloor}\]
可以线筛预处理F,或者暴力枚举质数（这个复杂度我不能确定）,按照素数粗略个数n/logn以及调和级数求和nlogn来看暴力的复杂度接近On
处理完F以后就是喜闻乐见的下底函数分块
\[\sum_{isprime(p)}\sum_{d=1}^{\left \lfloor \frac{n}{p} \right \rfloor}\mu(d){\left \lfloor \frac{n}{pd} \right \rfloor}{\left \lfloor \frac{m}{pd} \right \rfloor}\]
将pd设为k
\[\sum_{k=1}^{n}\sum_{isprime(p) \land p|k}\mu(\frac{k}{p}){\left \lfloor \frac{n}{k} \right \rfloor}{\left \lfloor \frac{m}{k} \right \rfloor}\]
\[\sum_{k=1}^{n}F(k){\left \lfloor \frac{n}{k} \right \rfloor}{\left \lfloor \frac{m}{k} \right \rfloor}\]
可以线筛预处理F,或者暴力枚举质数（这个复杂度我不能确定）,按照素数粗略个数n/logn以及调和级数求和nlogn来看暴力的复杂度接近On
处理完F以后就是喜闻乐见的下底函数分块
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
#include<iostream> #include<cstdio> #include<cstring> #include<cstdlib> #include<set> #include<ctime> #include<vector> #include<queue> #include<algorithm> #include<map> #include<cmath> #define inf 1000000000 #define N 10000000 #define pa pair<int,int> #define ll long long using namespace std; 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-'0';ch=getchar();} return x*f; } int T,n,m,cnt; bool mark[10000005]; int pri[1000005],mu[10000005]; ll f[10000005]; void getphi() { mu[1]=1; for(int i=2;i<=N;i++) { if(!mark[i])pri[++cnt]=i,mu[i]=-1; for(int j=1;j<=cnt&&pri[j]*i<=N;j++) { mark[i*pri[j]]=1; if(i%pri[j]==0){mu[i*pri[j]]=0;break;} else mu[i*pri[j]]=-mu[i]; } } for(int i=1;i<=cnt;i++) { int p=pri[i]; for(int j=1;j*p<=N;j++)f[j*p]+=mu[j]; } for(int i=1;i<=N;i++)f[i]+=f[i-1]; } int main() { getphi(); T=read(); while(T--) { ll ans=0; n=read();m=read(); if(n>m)swap(n,m); for(int i=1,j;i<=n;i=j+1) { j=min(n/(n/i),m/(m/i)); ans+=(f[j]-f[i-1])*(n/i)*(m/i); } printf("%lld\n",ans); } return 0; } |
计数器 9787792
OI 课件=>
OI 课件=>
学长怎么分析出O(n)的，难道不是总共更新（n/1+n/2+n/3+n/4+…+n/n）=nlogn次？
楼上的、、
线筛不能处理所有质因数的mu和，只能拉出来
如 42=2*3*7 2可以和21计算出 统计2的贡献 3可以和14计算出 统计3的贡献 但是7和6中的7也应该有贡献，但7不会和6算，6也不会和7算
所以线筛并不能统计出每个包含质因数的两因子相乘的情况、、
如有错请轻喷 (⊙ω⊙)
黄学长，哪个预处理其实不用O(nlogn)，可以直接在线性筛上加两句话，达到O(n)…OwO
那个看不太懂啊
话说..请问…第四个公式是怎么变到第五个公式的….
就是把莫比乌斯函数提前啊OwO