結果
問題 | No.1164 GCD Products hard |
ユーザー | 👑 emthrm |
提出日時 | 2020-08-13 17:23:21 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 222 ms / 2,500 ms |
コード長 | 1,678 bytes |
コンパイル時間 | 2,143 ms |
コンパイル使用メモリ | 204,064 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-09 19:21:12 |
合計ジャッジ時間 | 6,380 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 141 ms
5,248 KB |
testcase_01 | AC | 174 ms
5,248 KB |
testcase_02 | AC | 127 ms
5,248 KB |
testcase_03 | AC | 43 ms
5,248 KB |
testcase_04 | AC | 44 ms
5,248 KB |
testcase_05 | AC | 147 ms
5,248 KB |
testcase_06 | AC | 177 ms
5,248 KB |
testcase_07 | AC | 179 ms
5,248 KB |
testcase_08 | AC | 169 ms
5,248 KB |
testcase_09 | AC | 124 ms
5,248 KB |
testcase_10 | AC | 43 ms
5,248 KB |
testcase_11 | AC | 136 ms
5,248 KB |
testcase_12 | AC | 184 ms
5,248 KB |
testcase_13 | AC | 110 ms
5,248 KB |
testcase_14 | AC | 107 ms
5,248 KB |
testcase_15 | AC | 183 ms
5,248 KB |
testcase_16 | AC | 123 ms
5,248 KB |
testcase_17 | AC | 147 ms
5,248 KB |
testcase_18 | AC | 127 ms
5,248 KB |
testcase_19 | AC | 48 ms
5,248 KB |
testcase_20 | AC | 73 ms
5,248 KB |
testcase_21 | AC | 197 ms
5,248 KB |
testcase_22 | AC | 2 ms
5,248 KB |
testcase_23 | AC | 178 ms
5,248 KB |
testcase_24 | AC | 222 ms
5,248 KB |
testcase_25 | AC | 2 ms
5,248 KB |
testcase_26 | AC | 2 ms
5,248 KB |
testcase_27 | AC | 1 ms
5,248 KB |
testcase_28 | AC | 2 ms
5,248 KB |
ソースコード
#define _USE_MATH_DEFINES #include <bits/stdc++.h> using namespace std; #define FOR(i,m,n) for(int i=(m);i<(n);++i) #define REP(i,n) FOR(i,0,n) #define ALL(v) (v).begin(),(v).end() using ll = long long; const int INF = 0x3f3f3f3f; const ll LINF = 0x3f3f3f3f3f3f3f3fLL; const double EPS = 1e-8; const int MOD = 1000000007; // const int MOD = 998244353; const int dy[] = {1, 0, -1, 0}, dx[] = {0, -1, 0, 1}; const int dy8[] = {1, 1, 0, -1, -1, -1, 0, 1}, dx8[] = {0, -1, -1, -1, 0, 1, 1, 1}; template <typename T, typename U> inline bool chmax(T &a, U b) { return a < b ? (a = b, true) : false; } template <typename T, typename U> inline bool chmin(T &a, U b) { return a > b ? (a = b, true) : false; } struct IOSetup { IOSetup() { cin.tie(nullptr); ios_base::sync_with_stdio(false); cout << fixed << setprecision(20); } } iosetup; vector<bool> sieve_of_eratosthenes(int val) { vector<bool> res(val + 1, true); res[0] = false; if (val >= 1) res[1] = false; for (int i = 2; i * i <= val; ++i) { if (res[i]) { for (int j = i * i; j <= val; j += i) res[j] = false; } } return res; } ll mod_pow(ll base, ll exponent, int md = MOD) { base %= md; ll res = 1; while (exponent > 0) { if (exponent & 1) (res *= base) %= md; (base *= base) %= md; exponent >>= 1; } return res; } int main() { int a, b, n; cin >> a >> b >> n; vector<bool> ps = sieve_of_eratosthenes(b); ll ans = 1; FOR(i, 2, b + 1) { if (!ps[i]) continue; ll p = 0; for (ll j = i; j <= b; j *= i) (p += mod_pow(b / j - (a - 1) / j, n, MOD - 1)) %= MOD - 1; (ans *= mod_pow(i, p, MOD)) %= MOD; } cout << ans << '\n'; return 0; }