fork download
copy 
  1. /* 29 . 03 . 2008 */ 
  2. #include <bits/stdc++.h>
  3. using namespace std ;
  4.  
  5. bool watbor = 1;
  6.  
  7. #define int long long
  8. typedef long long ll ;
  9. typedef vector<int> vi ;
  10. typedef vector<pair<int,int>> vii ;
  11. typedef pair<int,int> pii ;
  12. typedef pair<ll,int> pli ;
  13. typedef pair<int,ll> pil ;
  14. typedef pair<ll,ll> pll ;
  15.  
  16. #define FOR(i,a,b) for(int i(a) ; i <= (int)b ; i++)
  17. #define FORD(i,a,b) for(int i(a) ; i >= (int)b ; i--)
  18. #define FORN(i,a,b) for(int i(a) ; i < (int)b ; i++)
  19. #define all(a) a.begin() , a.end()
  20. #define pb push_back
  21. #define fi first
  22. #define se second
  23. #define endl '\n' 
  24. #define BIT(mask,i) ((mask>>i)&1)
  25. #define builtin_popcount builtin_popcountll
  26. #define uni(a) sort(all(a)), a.resize(unique(all(a))-a.begin()) 
  27. #define MASK(a) (1ll << a) 
  28.  
  29. int gcd(int x, int y) {return __gcd(x, y) ;}
  30. int lg(int x) {return __lg(x) ;}
  31. int lcm(int x, int y) {return x / __gcd(x, y) * y ;}
  32.  
  33. template <class T> bool maxi(T &x,T y) { if (x < y) { x = y ; return true ;} return false ;}
  34. template <class T> bool mini(T &x,T y) { if (x > y) { x = y ; return true ;} return false ;}
  35.  
  36. const int N = 2e5 + 5, M = 5e3 + 5, LG = __lg(N) + 1, base = 311 ;
  37. const int oo = 2e9, sm = 1e9 + 7, mod1 = 1e9 + 7, mod2 = 998244353 ;
  38. const long long inf = 1e18 ;
  39.  
  40. int n, m; 
  41.  
  42. void init(){
  43. 	cin >> n >> m;
  44. }
  45.  
  46. int isFS[N + 5], preFS[N + 5];
  47.  
  48. int checkFS(int x){
  49. 	int chanle = 0;
  50. 	for (int i = 2; 1ll * i * i <= x; i++) if(x % i == 0){
  51. 		int cnt = 0;
  52. 		chanle++;
  53. 		while(x % i == 0){
  54. 			cnt++;
  55. 			x /= i;
  56. 		}
  57. 		if(cnt > 1) return 0 ;
  58. 	}
  59.  
  60. 	if(n != 1)
  61. 		chanle++;
  62.  
  63. 	if(chanle % 2 == 0) return -1;
  64. 	return 1;
  65. }
  66.  
  67. void buildFreeSquare(){
  68. 	FOR(i, 2, N) 
  69. 		isFS[i] = checkFS(i);
  70.  
  71. 	FOR(i, 1, N)
  72. 		preFS[i] = preFS[i - 1] + isFS[i];
  73. }
  74.  
  75. void solve(){
  76. 	ll ans = 0; 
  77.  
  78. 	for(int i = 1; i <= n;){
  79. 		int u = n / i, v = m / i;
  80.  
  81. 		int j = 2e9;
  82. 		if(u != 0) j = min(j, n / u);
  83. 		if(v != 0) j = min(j, m / v);
  84.  
  85. 		ans+= (n / i) * (m / i) * (preFS[j] - preFS[i - 1]);
  86. 		i = j + 1;
  87. 	}
  88.  
  89. 	cout << m * n - ans << "\n";
  90. }
  91.  
  92. signed main(){
  93.     ios_base::sync_with_stdio(0) ; cin.tie(0) ; cout.tie(0) ; 
  94.  
  95.     #define task "cpcnt"
  96.     if(fopen(task".inp","r")){
  97.         freopen(task".inp","r",stdin) ; 
  98.         freopen(task".out","w",stdout) ; 
  99.     }
  100.  
  101.     int tc ; tc = 1 ;
  102.     if(watbor) cin >> tc ;
  103.  
  104.     buildFreeSquare();
  105.  
  106.     FOR(bqc, 1, tc) {
  107.         init() ;
  108.         solve() ;
  109.     }
  110.  
  111.     cerr << "\nTime : " << clock() * 0.001 << "s" << endl ;
  112.     return 0 ; 
  113. }
  114. /* Watbor */
Success #stdin #stdout #stderr 0.15s 6892KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
0
stderr
copy 
Time : 149.956s
https://ideone.com/zJjcuh
language:
C++14 (gcc 8.3)
created:
6 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!