結果

問題 No.1164 GCD Products hard
ユーザー Navier_Boltzmann
提出日時 2023-12-31 21:49:44
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 942 bytes
コンパイル時間 5,547 ms
コンパイル使用メモリ 309,556 KB
実行使用メモリ 74,092 KB
最終ジャッジ日時 2024-09-27 17:12:23
合計ジャッジ時間 15,750 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample -- * 2
other WA * 2 TLE * 5 -- * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>


using namespace std;
using namespace atcoder;
#define rep(i,m,n) for (int i = (int)(m); i < (int)(n); i++)
#define ll long long
#define modint modint1000000007

const ll MOD = 1000000007;

long long pow(long long x, long long n, long long mod) {
    long long ret = 1;
    while (n > 0) {
        if (n & 1) ret = ret * x % mod;  // n の最下位bitが 1 ならば x^(2^i) をかける
        x = x * x % mod;
        n >>= 1;  // n を1bit 左にずらす
    }
    return ret;
}

int main(){

    ll A,B,N;
    cin >> A >> B >> N;
    vector<ll> cnt(B+1,0);
    for(ll i=B;i>0;i--){
        cnt[i] = (cnt[i] + pow(B/i - (A-1)/i,N,MOD-1))%(MOD-1);
        for(ll j=2*i;j < B+1;j+=i){
            cnt[i] = (cnt[i] - cnt[j])%(MOD-1);
        }
    }
    ll ans = 1;
    rep(i,1,B+1){
        ans *= pow((ll)(i),cnt[i],MOD);
        ans %= MOD;
    };
    cout << ans << endl;
    return 0;
}
0