Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- /*
- Shahadat Hossain
- I.C.T Department
- Comilla University
- Session: 2013-2014
- */
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- typedef unsigned long long ull;
- #define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
- #define UNIQUE(x) x.erase(unique(all(x)), x.end())
- #define fs first
- #define sc second
- #define pb push_back
- #define sz(x) (int)x.size()
- #define all(v) v.begin(),v.end()
- #define D(x) cerr << #x " = " << x << '\n'
- #define ms(a,b) memset(a, b, sizeof(a))
- #define valid(x,y,n, m) x>=0 && y>=0 && x<n && y<m
- #define input freopen("/Users/shahadat/Desktop/input.txt", "r", stdin)
- #define output freopen("/Users/shahadat/Desktop/output.txt", "w", stdout)
- #define endl '\n'
- #define eps 1e-5
- #define yes printf("Yes\n")
- #define no printf("No\n")
- #define int long long
- inline void fast(){
- ios_base::sync_with_stdio(false);
- cin.tie(NULL); cout.tie(NULL);
- }
- //mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
- //uniform_int_distribution<int>(10, 20)(rng);
- int gcd(int n,int m){return m==0?n:gcd(m,n%m);}
- inline int Set(int n,int pos) { return n = n | (1LL << pos); }
- inline int Reset(int n,int pos) { return n = n & ~(1LL << pos); }
- inline bool Check(int n,int pos) { return (bool)(n & (1LL << pos)); }
- inline int Count(ll n) { return __builtin_popcountll(n); }
- typedef pair<int,int> pint;
- int const N = 1e6 + 10;
- vector<int> prime[N];
- long long res[N];
- int ar[N];
- void sieve(){
- for(int i = 2; i < N; i++){
- if(prime[i].size()) continue;
- for(int j = i; j < N; j += i){
- prime[j].push_back(i);
- }
- }
- }
- long long foo(int n){
- int len = (int)prime[n].size();
- long long ret = 0;
- for(int i = 1; i < (1 << len); i++){
- int temp = 1;
- int cnt = 0;
- for(int pos = 0; pos < len; pos++){
- if(Check(i, pos)){
- temp *= prime[n][pos];
- cnt++;
- }
- }
- if(cnt & 1) ret += ar[temp];
- else ret -= ar[temp];
- ar[temp] += n;
- }
- return ret ;
- }
- void pre(){
- for(int i = 2; i < N; i++){
- res[i] = foo(i);
- }
- }
- int32_t main(){
- sieve();
- pre();
- int t;
- scanf("%lld", &t);
- while(t--){
- int n;
- scanf("%lld", &n);
- printf("%lld\n", res[n]);
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement