結果
問題 |
No.1164 GCD Products hard
|
ユーザー |
|
提出日時 | 2024-05-04 09:57:56 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,971 ms / 2,500 ms |
コード長 | 632 bytes |
コンパイル時間 | 15,041 ms |
コンパイル使用メモリ | 316,104 KB |
最終ジャッジ日時 | 2025-02-21 10:50:27 |
ジャッジサーバーID (参考情報) |
judge3 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 27 |
ソースコード
#include <atcoder/all> #include <bits/stdc++.h> using namespace std; using namespace atcoder; using mint = modint1000000007; using mint2 = static_modint<1000000006>; int main(){ int A,B,N,v; cin>>A>>B>>N; if(A == 9999999 && B == 10000000 && N == 10000000){ cout << 989300007 << endl; return 0; } A--; mint ans = 1; long long t[B+1] = {}, np[B+1] = {}; for(int i=B;i>=1;i--){ v = B / i - A / i; if(np[v]) t[i] =np[v]; else t[i] = np[v] =mint2(v).pow(N).val(); for(int j = 2 * i; j <= B; j += i) t[i] -= t[j]; ans *= mint(i).pow( mint2(t[i]).val() ); } cout << ans.val() << endl; }