SHARE
TWEET

Untitled

a guest Sep 20th, 2019 97 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*
  2.  Shahadat Hossain
  3.  I.C.T Department
  4.  Comilla University
  5.  Session: 2013-2014
  6.  */
  7.  
  8. #include<bits/stdc++.h>
  9. using namespace std;
  10.  
  11. typedef long long ll;
  12. typedef unsigned long long ull;
  13.  
  14. #define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
  15. #define UNIQUE(x)       x.erase(unique(all(x)), x.end())
  16.  
  17. #define fs              first
  18. #define sc              second
  19. #define pb              push_back
  20.  
  21. #define sz(x)           (int)x.size()
  22. #define all(v)          v.begin(),v.end()
  23. #define D(x)            cerr << #x " = " << x << '\n'
  24. #define ms(a,b)         memset(a, b, sizeof(a))
  25. #define valid(x,y,n, m)      x>=0 && y>=0 && x<n && y<m
  26.  
  27. #define input           freopen("/Users/shahadat/Desktop/input.txt", "r", stdin)
  28. #define output          freopen("/Users/shahadat/Desktop/output.txt", "w", stdout)
  29.  
  30. #define endl            '\n'
  31. #define eps             1e-5
  32. #define yes             printf("Yes\n")
  33. #define no              printf("No\n")
  34.  
  35. #define int             long long
  36.  
  37. inline void fast(){
  38.     ios_base::sync_with_stdio(false);
  39.     cin.tie(NULL); cout.tie(NULL);
  40. }
  41.  
  42. //mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  43. //uniform_int_distribution<int>(10, 20)(rng);
  44.  
  45. int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
  46. inline int Set(int n,int pos) { return n = n | (1LL << pos); }
  47. inline int Reset(int n,int pos) { return n = n & ~(1LL << pos); }
  48. inline bool Check(int n,int pos) { return (bool)(n & (1LL << pos)); }
  49. inline int Count(ll n) { return __builtin_popcountll(n); }
  50. typedef pair<int,int> pint;
  51.  
  52. int const N = 1e6 + 10;
  53. vector<int> prime[N];
  54. long long res[N];
  55. int ar[N];
  56.  
  57. void sieve(){
  58.     for(int i = 2; i < N; i++){
  59.         if(prime[i].size()) continue;
  60.         for(int j = i; j < N; j += i){
  61.             prime[j].push_back(i);
  62.         }
  63.     }
  64. }
  65.  
  66. long long foo(int n){
  67.     int len = (int)prime[n].size();
  68.     long long ret = 0;
  69.    
  70.     for(int i = 1; i < (1 << len); i++){
  71.         int temp = 1;
  72.         int cnt = 0;
  73.         for(int pos = 0; pos < len; pos++){
  74.             if(Check(i, pos)){
  75.                 temp *= prime[n][pos];
  76.                 cnt++;
  77.             }
  78.         }
  79.         if(cnt & 1) ret += ar[temp];
  80.         else ret -= ar[temp];
  81.         ar[temp] += n;
  82.     }
  83.     return ret ;
  84. }
  85.  
  86.  
  87.  
  88. void pre(){
  89.     for(int i = 2; i < N; i++){
  90.         res[i] = foo(i);
  91.     }
  92. }
  93.  
  94. int32_t main(){
  95.     sieve();
  96.     pre();
  97.    
  98.     int t;
  99.     scanf("%lld", &t);
  100.    
  101.     while(t--){
  102.         int n;
  103.         scanf("%lld", &n);
  104.         printf("%lld\n", res[n]);
  105.     }
  106. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top