首页 > 代码库 > bzoj2820 YY的GCD
bzoj2820 YY的GCD
2820: YY的GCD
Time Limit: 10 Sec Memory Limit: 512 MBSubmit: 1296 Solved: 672
[Submit][Status][
id=2820" style="color:blue; text-decoration:none">Discuss]
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
莫比乌斯反演
与bzoj2301类似。答案ans=∑(p)∑(1≤d≤n/p)mu[d]*(n/pd)*(n/pd)。
令T=pd,则ans=∑(1≤T≤n)(n/T)*(m/T)∑(p|T)mu[T/p]。
设f(T)=∑(p|T)mu[T/p]。假设能预处理出f(T)和前缀和,则採用分块就能够在O(sqrt(n))复杂度内完毕单次询问。
怎样预处理?仅仅须要枚举每个质数,暴力改动它的全部倍数就可以。由于每个质数的改动次数均摊ln(n),而n以内质数个数接近n/ln(n)。则总复杂度是约等于O(n)的。
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> #define F(i,j,n) for(int i=j;i<=n;i++) #define D(i,j,n) for(int i=j;i>=n;i--) #define ll long long #define maxn 10000000 using namespace std; int n,m,t,tot; int pri[maxn+5],mu[maxn+5]; ll f[maxn+5]; bool mark[maxn+5]; inline 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; } inline void getmu() { mu[1]=1; F(i,2,maxn) { if (!mark[i]) pri[++tot]=i,mu[i]=-1; for(int j=1;j<=tot&&i*pri[j]<=maxn;j++) { mark[i*pri[j]]=true; if (i%pri[j]==0){mu[i*pri[j]]=0;break;} else mu[i*pri[j]]=-mu[i]; } } F(i,1,tot) for(int j=1;j*pri[i]<=maxn;j++) f[j*pri[i]]+=mu[j]; F(i,1,maxn) f[i]+=f[i-1]; } int main() { getmu(); t=read(); while (t--) { ll ans=0; n=read();m=read(); if (n>m) swap(n,m); for(int i=1,pos;i<=n;i=pos+1) { pos=min(n/(n/i),m/(m/i)); ans+=(f[pos]-f[i-1])*(n/i)*(m/i); } printf("%lld\n",ans); } return 0; }
bzoj2820 YY的GCD
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。