首页 > 代码库 > BZOJ2301 [HAOI2011]Problem b
BZOJ2301 [HAOI2011]Problem b
什么东西。。。
搞了半天Mobius反演到底是什么还是没搞定。。。(至少会求了嘛。。。好不好)
但是程序写出来了^_^,可惜意义不明T T
1 /************************************************************** 2 Problem: 2301 3 User: rausen 4 Language: C++ 5 Result: Accepted 6 Time:10604 ms 7 Memory:1244 kb 8 ****************************************************************/ 9 10 #include <cstdio>11 #include <cmath>12 #include <algorithm>13 14 using namespace std;15 typedef long long ll;16 const int N = 50005;17 int T;18 int u[N], p[N], tot;19 bool v[N];20 21 inline int read(){22 int x = 0;23 char ch = getchar();24 while (ch < ‘0‘ || ch > ‘9‘)25 ch = getchar();26 27 while (ch >= ‘0‘ && ch <= ‘9‘){28 x = x * 10 + ch - ‘0‘;29 ch = getchar();30 }31 return x;32 }33 34 void pre_work(){35 u[1] = 1;36 int i, j, K;37 for (i = 2; i < N; ++i){38 if (!v[i])39 p[++tot] = i, u[i] = -1;40 for (j = 1; i * p[j] < N && j <= tot; ++j){41 v[K = i * p[j]] = 1;42 if (i % p[j] == 0){43 u[K] = 0; 44 break;45 }else u[K] = -u[i];46 }47 }48 for (i = 2; i < N; ++i)49 u[i] += u[i - 1];50 }51 52 ll work(int n, int m, int k){53 n /= k, m /= k;54 if (n > m) swap(n, m);55 ll res = 0;56 int i, last;57 for (i = 1; i <= n; i = last + 1){58 last = min(n / (n / i), m / (m / i));59 res += (ll) (u[last] - u[i - 1]) * (n / i) * (m / i);60 }61 return res;62 }63 64 int main(){65 T = read();66 pre_work();67 int a, b, c, d, k;68 ll ans;69 while (T--){70 a = read(), b = read(), c = read(), d = read(), k = read();71 ans = work(b, d, k) - work(a - 1, d, k) - work(b, c - 1, k) + work(a - 1, c - 1, k);72 printf("%lld\n", ans);73 }74 return 0;75 }
BZOJ2301 [HAOI2011]Problem b
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。