fork download
copy 
  1. #include<bits/stdc++.h>
  2. #define ll long long
  3. #define ull unsigned long long
  4. #define nl '\n'
  5. #define mod 1000000007
  6. #define fori(i,n) for(ll i=0;i < n;i++)
  7. #define forn(i,n) for(ll i=1;i <= n;i++)
  8. #define forx(i,x,n) for(ll i=x;i < n;i++)
  9. #define sortx(x) sort(x.begin(),x.end())
  10. #define sorty(x) sort(x.begin(),x.end(),greater<>())
  11. using namespace std;
  12. /*#include <ext/pb_ds/assoc_container.hpp>
  13. #include <ext/pb_ds/tree_policy.hpp>
  14. using namespace __gnu_pbds;
  15. template<typename T>
  16. using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
  17. using namespace __gnu_pbds;
  18. #define ordered_multiset tree<int, null_type, less_equal<int>, rb_tree_tag, tree_order_statistics_node_update>
  19.  
  20. ll Mod(ll base, ll exp, ll MOD){
  21.     if(exp == 0) return 1;
  22.     ll res = Mod(base,exp/2,MOD);
  23.     if(exp % 2) 
  24.       return (((res * res) % MOD)*base) % MOD;
  25.     else
  26.       return (res*res) % MOD;
  27. }
  28.  
  29. ll gcd(ll x,ll y){
  30.   ll b = min(x,y);
  31.   ll a = max(x,y);
  32.   while(b != 0){
  33.     ll temp = b;
  34.     b = a % b;
  35.     a = temp;
  36.   }
  37.   return a;
  38. }
  39.  
  40. ll div(vector<ll> &x){
  41.   for(ll i=1;i <= 1000007;i++){
  42.     for(ll j=i;j <= 1000007;j+=i){
  43.       x[j]++;
  44.     }
  45.   }
  46. }
  47.  
  48. bool prime(ll n){
  49.   int c=0;
  50.   for(ll i=1;i <= n;i++){
  51.     if(n % i == 0) c++;
  52.     if(c > 2) break;
  53.   }
  54.   if(c == 2) return true;
  55.   return false;
  56. }*/
  57.  
  58. vector<int> computeTotient(int N) {
  59.     vector<int> phi(N + 1);
  60.     for (int i = 1; i <= N; i++)
  61.         phi[i] = i;
  62.  
  63.     for (int i = 2; i <= N; i++) {
  64.         if (phi[i] == i){
  65.             for (int j = i; j <= N; j += i) {
  66.                 phi[j] = phi[j] * (i - 1) / i;
  67.             }
  68.         }
  69.     }
  70.     return phi;
  71. }
  72.  
  73. ll countPairs(int N) {
  74.     vector<int> phi = computeTotient(N);
  75.     ll S = 0;
  76.     for (int i = 1; i <= N; i++) {
  77.         S += phi[i];
  78.     }
  79.  
  80.     // Compute total pairs
  81.     ll totalPairs = (1LL * N * (N + 1)) / 2;
  82.  
  83.     // Pairs with gcd > 1 = Total pairs - Coprime pairs
  84.     return totalPairs - S;
  85. }
  86.  
  87. int main() {
  88.     ios_base::sync_with_stdio(false);
  89.     cin.tie(nullptr);
  90.     int t,i=1;
  91.     cin >> t;
  92.     while(t--){
  93.       int N;
  94.       cin >> N;
  95.       cout << "Case " << i << ": " << countPairs(N) << nl;
  96.       i++;
  97.     }
  98. }
Success #stdin #stdout 0s 5276KB
comments (?)
stdin
copy 
3
3
4
6
stdout
copy 
Case 1: 2
Case 2: 4
Case 3: 9
https://ideone.com/TNnbta
language:
C++14 (gcc 8.3)
created:
20 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!