結果

問題 No.1022 Power Equation
コンテスト
ユーザー Im_Gimlet
提出日時 2020-09-07 02:15:42
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 1,601 bytes
コンパイル時間 1,580 ms
コンパイル使用メモリ 170,952 KB
実行使用メモリ 142,120 KB
最終ジャッジ日時 2024-11-29 08:00:09
合計ジャッジ時間 17,347 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample WA * 1
other WA * 3 TLE * 5
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
using ll = long long;
using P = pair<ll, ll>;
const long double PI = acos(-1.0L);
ll GCD(ll a, ll b) { return b?GCD(b, a%b):a; }
ll LCM(ll a, ll b) { return a/GCD(a, b)*b; }

int t;

int main() {
    cin >> t;
    while(t--) {
        ll n; cin >> n;
        ll ans = n*n;   // a=c=1のときb,dはどの組み合わせでもよい
        if(n == 1) {
            cout << ans << endl;
            continue;
        }
        ll limit = sqrtl(n);
        vector<bool> num(n+1, true);
        num[0] = false;
        num[1] = false;
        for(ll i = 2; i <= limit; ++i) {
            // a = i
            if(num[i]) {
                ll cnt = 1;
                ll now = i;
                while(1) {
                    if(now*i > n) break;
                    now *= i;
                    cnt++;
                }

                for(ll j = 1; j <= cnt; ++j) {
                    // a = i^j
                    ll a = powl(i, j);
                    num[a] = false;
                    for(ll k = j; k <= cnt; ++k) {
                        // cout << "a=" << a << " c=" << powl(i, k) << endl;
                        if(k == j) ans += n;
                        else ans += ((n/k)*2);
                    }
                }
            }
        }
        for(ll i = limit+1; i <= n; ++i) if(num[i]) ans += n;

        cout << ans << endl;
    }
}
0