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. ll ways(ll n){
  59.   ll count = 0;
  60.   for(ll i=2;i <= n;i++){
  61.     for(ll j=i;j <= n;j++){
  62.       if(gcd(i,j) > 1) count++;
  63.     }
  64.   }
  65.   return count;
  66. }
  67.  
  68. int main() {
  69.     ios::sync_with_stdio(false);
  70.     cin.tie(nullptr);
  71.     int t;
  72.     cin >> t;
  73.     while(t--){
  74.       ll n;
  75.       cin >> n;
  76.       cout << ways(n) << nl;
  77.     }
  78. }
  79.  
Success #stdin #stdout 0s 5288KB
comments ()
stdin
copy 
2
3
4
stdout
copy 
2
4
https://ideone.com/PJK7xw
language:
C++14 (gcc 8.3)
created:
26 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!