# Mathematically Hard

May 13th, 2021
755
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. #include <bits/stdc++.h>
2. #define Niloy
3. #define int int64_t
4. #define mx (int) 5e6 + 123
5. #define MOD (int) 1e9 + 7
6. #define pb push_back
7. #define pairs pair<int, int>
8. #define vi vector<int>
9. #define vb vector<bool>
10. #define vii vector<pairs>
11. #define lb lower_bound
12. #define ub upper_bound
13. #define endl '\n'
14. #define llu unsigned long long
15. using namespace std;
16. /* ----------------------------------------------------------------------------------- */
17.
18. // Input/Output
19. #define fastInput ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
20. #define all(x) x.begin(), x.end()
21. #define square(a) (a * a)
22. #define mem(a, b) memset(a, b, sizeof(a))
23.
24. // Fractional Number
25. #define fraction()        cout.unsetf(ios::floatfield); cout.precision(10); cout.setf(ios::fixed, ios::floatfield);
26.
27. // Direction Array
28. int dx[] = {0, 0, 1, -1, 1, 1, -1, -1};
29. int dy[] = {1, -1, 0, 0, 1, -1, 1, -1};
30.
31. // File I/O
32. #define read(x)  freopen(x, "r", stdin);
33. #define write(x) freopen(x, "w", stdout);
34.
35. // Loops
36. #define rep(i, a, n) for (int i = a; i < n; i++)
37. #define REP(i, a, n) for (int i = a; i <= n; i++)
38. #define rev(i, n, a) for (int i = n - 1; i >= a; i--)
39. #define REV(i, n, a) for (int i = n; i >= a; i--)
40.
41. /* ----------------------------------------------------------------------------------- */
42.
43. #define Cases  cout << "Case " << ++Case << ": ";
44. #define __test int tt; int Case=0; cin >> tt; while(tt--)
45. #define showTime cerr << "time = " << (clock() / CLOCKS_PER_SEC) << " sec" << '\n';
46.
47. #define dbgA2(A, n, m) {cout<<"--> "<<#A<<" = \n";rep(i, 0, n){rep(j, 0, m){cout<<A[i][j]<<"";}cout<<"\n";}cout<<"\n";}
48. #define dbgA(A, n) {cout<<" --> "<<#A<<" = (";rep(i, 0, n)cout<<A[i]<<" ";cout<<")\n";}
49. #define dbg(args...) {string sss(#args);sss+=',';cout<<" --> ";debugger::call(all(sss), args);cout<<"\n";}
50.
51. /* ----------------------------------------------------------------------------------- */
52.
53. int gcd(int n, int m) { return m ? gcd(m, n % m) : n; }
54. int lcm(int n, int m) { return n / gcd(n, m) * m; }
55.
56. struct debugger {
57.     typedef string::iterator si;
58.     static void call(si it, si ed) {}
59.     template<typename T, typename ... aT>
60.     static void call(si it, si ed, T a, aT... rest) {
61.         string b;
62.         for(; *it!=','; ++it)
63.             if(*it!=' ')
64.                 b+=*it;
65.         cout << b << "=" << a << " ";
66.         call(++it, ed, rest...);
67.     }
68. };
69.
70. /* ----------------------------------------------------------------------------------- */
71. void input() {
72. #ifdef Niloy
74.     write("output.txt");
75. #endif
76. }
77.
78. /* ----------------------------------------------------------------------------------- */
79.
80. llu phi[mx];
81.
82. void generatePhi(int n) {
83.     REP(i, 1, n) {
84.         phi[i] = i;
85.     }
86.
87.     REP(i, 2, n) {
88.         if (phi[i] == i) {
89.             for (int j = i; j <= n; j += i) {
90.                 phi[j] *= (i - 1);
91.                 phi[j] /= i;
92.             }
93.         }
94.     }
95. }
96.
97. void solve() {
98.     int a, b;
99.     cin >> a >> b;
100.     cout << phi[b] - phi[a - 1] << endl;
101. }
102.
103. int32_t main() {
104.     fastInput;
105.     // solve();
106.     int lim = 5e6;
107.     generatePhi(lim);
108.
109.     REP(i, 1, lim) {
110.         phi[i] *= phi[i];
111.     }
112.
113.     REP(i, 1, lim) {
114.         phi[i] += phi[i - 1];
115.     }
116.
117.     __test {
118.         Cases;
119.         solve();
120.     }
121.
122.     return 0;
123. }
RAW Paste Data