首页 > 代码库 > bzoj 1101 [POI2007]Zap - 莫比乌斯反演
bzoj 1101 [POI2007]Zap - 莫比乌斯反演
<style></style>
Description
FGD正在破解一段密码,他需要回答很多类似的问题:对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a ,y<=b,并且gcd(x,y)=d。作为FGD的同学,FGD希望得到你的帮助。
Input
第一行包含一个正整数n,表示一共有n组询问。(1<=n<= 50000)接下来n行,每行表示一个询问,每行三个 正整数,分别为a,b,d。(1<=d<=a,b<=50000)
Output
对于每组询问,输出到输出文件zap.out一个正整数,表示满足条件的整数对数。
Sample Input
2
4 5 2
6 4 3
4 5 2
6 4 3
Sample Output
3
2
//对于第一组询问,满足条件的整数对有(2,2),(2,4),(4,2)。对于第二组询问,满足条件的整数对有(
6,3),(3,3)。
2
//对于第一组询问,满足条件的整数对有(2,2),(2,4),(4,2)。对于第二组询问,满足条件的整数对有(
6,3),(3,3)。
题目大意 (这道题够短了吧,不需要大意了)
这道题的目标是求。
根据gcd的性质,等价于求。
然后看看上一道题的“套路”,发现它的解法2可以支持多组数据。然后思考,发现莫比乌斯函数和欧拉函数有类似的性质:。赶紧抓过来化简式子。
然后又得到了这个优美的式子。然后发现莫比乌斯函数的系数的取值并不多,所以可以分段求值,然后就可以把这道题水掉了。
(说实话,我并不觉得这算莫比乌斯反演,只是用到了莫比乌斯函数的性质罢了。当个入门题练练手吧)
Code
1 /** 2 * bzoj 3 * Problem#1101 4 * Accepted 5 * Time:8956ms 6 * Memory:1576k 7 */ 8 #include <iostream> 9 #include <cstdio> 10 #include <ctime> 11 #include <cmath> 12 #include <cctype> 13 #include <cstring> 14 #include <cstdlib> 15 #include <fstream> 16 #include <sstream> 17 #include <algorithm> 18 #include <map> 19 #include <set> 20 #include <stack> 21 #include <queue> 22 #include <vector> 23 #include <list> 24 #ifndef WIN32 25 #define Auto "%lld" 26 #else 27 #define Auto "%I64d" 28 #endif 29 using namespace std; 30 typedef bool boolean; 31 const signed int inf = (signed)((1u << 31) - 1); 32 const signed long long llf = (signed long long)((1ull << 61) - 1); 33 const double eps = 1e-6; 34 const int binary_limit = 128; 35 #define smin(a, b) a = min(a, b) 36 #define smax(a, b) a = max(a, b) 37 #define max3(a, b, c) max(a, max(b, c)) 38 #define min3(a, b, c) min(a, min(b, c)) 39 template<typename T> 40 inline boolean readInteger(T& u){ 41 char x; 42 int aFlag = 1; 43 while(!isdigit((x = getchar())) && x != ‘-‘ && x != -1); 44 if(x == -1) { 45 ungetc(x, stdin); 46 return false; 47 } 48 if(x == ‘-‘){ 49 x = getchar(); 50 aFlag = -1; 51 } 52 for(u = x - ‘0‘; isdigit((x = getchar())); u = (u << 1) + (u << 3) + x - ‘0‘); 53 ungetc(x, stdin); 54 u *= aFlag; 55 return true; 56 } 57 58 const int limit = 5e4; 59 60 int n; 61 int a, b, d; 62 int num = 0; 63 int prime[10000]; 64 int miu[limit + 1]; 65 boolean vis[limit + 1]; 66 67 inline void Euler() { 68 memset(vis, false, sizeof(vis)); 69 miu[0] = 0, miu[1] = 1; 70 for(int i = 2; i <= limit; i++) { 71 if(!vis[i]) miu[i] = -1, prime[num++] = i; 72 for(int j = 0; j < num && prime[j] * 1LL * i <= limit; j++) { 73 int c = prime[j] * i; 74 vis[c] = true; 75 if((i % prime[j]) == 0) { 76 miu[c] = 0; 77 break; 78 } else { 79 miu[c] = -1 * miu[i]; 80 } 81 } 82 miu[i] += miu[i - 1]; 83 } 84 } 85 86 inline void init() { 87 readInteger(n); 88 } 89 90 long long res; 91 92 inline void solve() { 93 while(n--) { 94 readInteger(a); 95 readInteger(b); 96 readInteger(d); 97 a /= d, b /= d; 98 if(a > b) swap(a, b); 99 res = 0;100 for(int i = 1, j; i <= a; i = j + 1) {101 j = min(a / (a / i), b / (b / i));102 res += (a / j) * 1LL * (b / j) * (miu[j] - miu[i - 1]);103 }104 printf(Auto"\n", res);105 }106 }107 108 int main() {109 Euler();110 init();111 solve();112 return 0;113 }
bzoj 1101 [POI2007]Zap - 莫比乌斯反演
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。