Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <cstdlib>
- #include <cstdio>
- #include <algorithm>
- #include <map>
- #include <vector>
- #define llong long long
- using namespace std;
- const int INF = (int) 1e9 + 7;
- const int MXN = (int) 1e6 + 7;
- int t, n, m;
- int g[MXN];
- llong ans;
- llong f(llong d) {
- return (n / d) * (m / d);
- }
- int slow(int x, int y) {
- int c = 0;
- for (int i = 0; i <= x; i++)
- for (int j = 0; j <= y; j++)
- if (__gcd(i, j) == 1) c++;
- return c;
- }
- int main() {
- ios_base::sync_with_stdio(0);
- for (int i = 1; i < MXN; i++) {
- g[i] = 1;
- int cur = i;
- for (int d = 2; d * d <= cur; d++) {
- if (cur % d != 0)
- continue;
- int cnt = 0;
- while (cur % d == 0) {
- cur /= d;
- cnt++;
- }
- if (cnt >= 2) {
- g[i] = 0;
- break;
- }
- g[i] = -g[i];
- }
- if (cur > 1) g[i] = -g[i];
- }
- cin >> t;
- for (int cases = 1; cases <= t; cases++) {
- cin >> n >> m;
- if (m < n) swap(n, m);
- llong ans = 0;
- for (int i = 1; i <= n; i++)
- ans += f(i) * (llong) g[i];
- ans += 2;
- if (!n && !m) ans = 0;
- else if (!n || !m) ans = 1;
- cout << "Case " << cases << ": " << ans << "\n";
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement