题目描述
FGD正在破解一段密码,他需要回答很多类似的问题:对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a,y<=b,并且gcd(x,y)=d。作为FGD的同学,FGD希望得到你的帮助。
输入格式
第一行包含一个正整数n,表示一共有n组询问。(1<=n<= 50000)接下来n行,每行表示一个询问,每行三个正整数,分别为a,b,d。(1<=d<=a,b<=50000)
输出格式
对于每组询问,输出一个正整数,表示满足条件的整数对数。
题目解析
无限膜拜莫比乌斯反演和分块。
首先对题目条件做一个变换。令,则根据最大公约数的性质,有
观察上式,既有i,j互质,那么我们可以作进一步推导:
推导至(1)式使用了莫比乌斯函数的性质,(2)式运用乘法原理,变换求和指标,得到(3)式。至此,我们所求的结果可以用线性时间求出。
但是询问有50000个,这样做还是超时,考虑优化。注意到的取值最多只有
个,
同理。于是可以分块,把取值相同的一段合并一起算。用
预处理莫比乌斯函数及其前缀和,一次询问只需
时间,至此问题成功解决。
利用本题的思想,还可以解决类似的2301,此处不再展开。
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 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
/************************************************************** Problem: 1101 User: frank_c1 Language: C++ Result: Accepted Time:6684 ms Memory:1908 kb ****************************************************************/ #include <set> #include <map> #include <queue> #include <ctime> #include <cmath> #include <cstdio> #include <vector> #include <string> #include <cctype> #include <bitset> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,u) for(int i=fr[u];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ const int maxn=50005; bool check[maxn]; int pr[maxn],mu[maxn],sum[maxn]; int tot; void mu_table() { int n=50000; memset(check,0,sizeof(check)); sum[1]=mu[1]=1; tot=0; for(int i=2;i<=n;i++) { if(!check[i]) { pr[++tot]=i; mu[i]=-1; } for(int j=1;j<=tot;j++) { if(i*pr[j]>n) break; check[i*pr[j]]=true; if(i%pr[j]==0) { mu[i*pr[j]]=0; break; } else mu[i*pr[j]]=-mu[i]; } sum[i]=sum[i-1]+mu[i]; } } int main() { int T,a,b,d; mu_table(); read(T); while(T--) { read(a);read(b);read(d); a/=d;b/=d; int pos,mx=min(a,b); LL res=0; for(int i=1;i<=mx;i=pos+1) { pos=min(a/(a/i),b/(b/i)); res+=((LL)(a/i))*(b/i)*(sum[pos]-sum[i-1]); } printf("%lld\n",res); } return 0; } |