Guest User

Ray Gun

a guest
Sep 30th, 2016
325
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. #define f(i,a,b) for(int i = (a); i <= (b); i++)
  3.  
  4. typedef long long ll;
  5. using namespace std;
  6.  
  7. bool Ignore[1000005], U[1000005];
  8. int F[1000005], T;
  9. ll A, B;
  10.  
  11. inline ll cnt(ll x)
  12. {
  13.     if(F[x]&1) return - (B/x)*(A/x);
  14.     else return (B/x)*(A/x);
  15. }
  16.  
  17. int main()
  18. {
  19.     f(i,2,1000000)
  20.         if(!F[i])
  21.             for(int k = i; k <= 1000000; k += i)
  22.                 F[k]++;
  23.  
  24.     f(i,2,1000)
  25.         for(int k = i*i; k <= 1000000; k += i*i)
  26.             Ignore[k] = true;
  27.  
  28.     cin >> T;
  29.  
  30.     f(tt,1,T)
  31.     {
  32.         cin >> A >> B;
  33.         if(A > B) swap(A,B);
  34.  
  35.         if(A == 0)
  36.         {
  37.             if(B > 0) cout << "Case " << tt << ": 1\n";
  38.             else cout << "Case " << tt << ": 0\n";
  39.             continue;
  40.         }
  41.  
  42.         ll ans = 0;
  43.         f(i,1,A) if(!Ignore[i]) ans += cnt(i);
  44.         cout << "Case " << tt << ": " << ans + 2 << "\n";
  45.     }
  46. }
RAW Paste Data