結果
| 問題 | No.2798 Multiple Chain |
| ユーザー |
 kwm_t
|
| 提出日時 | 2024-06-28 22:51:02 |
| 言語 | C++23 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 2,881 bytes |
| コンパイル時間 | 3,131 ms |
| コンパイル使用メモリ | 258,928 KB |
| 実行使用メモリ | 10,752 KB |
| 最終ジャッジ日時 | 2024-06-28 22:51:08 |
| 合計ジャッジ時間 | 6,604 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 1 ms
8,320 KB |
| testcase_01 | TLE | - |
| testcase_02 | -- | - |
| testcase_03 | -- | - |
| testcase_04 | -- | - |
| testcase_05 | -- | - |
| testcase_06 | -- | - |
| testcase_07 | -- | - |
| testcase_08 | -- | - |
| testcase_09 | -- | - |
| testcase_10 | -- | - |
| testcase_11 | -- | - |
| testcase_12 | -- | - |
| testcase_13 | -- | - |
| testcase_14 | -- | - |
| testcase_15 | -- | - |
| testcase_16 | -- | - |
| testcase_17 | -- | - |
| testcase_18 | -- | - |
| testcase_19 | -- | - |
| testcase_20 | -- | - |
| testcase_21 | -- | - |
| testcase_22 | -- | - |
| testcase_23 | -- | - |
| testcase_24 | -- | - |
| testcase_25 | -- | - |
| testcase_26 | -- | - |
| testcase_27 | -- | - |
| testcase_28 | -- | - |
| testcase_29 | -- | - |
| testcase_30 | -- | - |
| testcase_31 | -- | - |
| testcase_32 | -- | - |
| testcase_33 | -- | - |
| testcase_34 | -- | - |
| testcase_35 | -- | - |
| testcase_36 | -- | - |
| testcase_37 | -- | - |
| testcase_38 | -- | - |
| testcase_39 | -- | - |
| testcase_40 | -- | - |
| testcase_41 | -- | - |
| testcase_42 | -- | - |
| testcase_43 | -- | - |
| testcase_44 | -- | - |
| testcase_45 | -- | - |
| testcase_46 | -- | - |
| testcase_47 | -- | - |
| testcase_48 | -- | - |
| testcase_49 | -- | - |
| testcase_50 | -- | - |
| testcase_51 | -- | - |
| testcase_52 | -- | - |
| testcase_53 | -- | - |
ソースコード
#include <bits/stdc++.h>
//#include <atcoder/all>
using namespace std;
//using namespace atcoder;
//using mint = modint1000000007;
//const int mod = 1000000007;
//using mint = modint998244353;
//const int mod = 998244353;
//const int INF = 1e9;
//const long long LINF = 1e18;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define rep2(i,l,r)for(int i=(l);i<(r);++i)
#define rrep(i, n) for (int i = (n) - 1; i >= 0; --i)
#define rrep2(i,l,r)for(int i=(r) - 1;i>=(l);--i)
#define all(x) (x).begin(),(x).end()
#define allR(x) (x).rbegin(),(x).rend()
#define P pair<int,int>
template<typename A, typename B> inline bool chmax(A & a, const B & b) { if (a < b) { a = b; return true; } return false; }
template<typename A, typename B> inline bool chmin(A & a, const B & b) { if (a > b) { a = b; return true; } return false; }
struct Miller {
const std::vector<long long> v = { 2 , 7 , 61 }; // < 4,759,123,141
// x^k (mod m)
long long modpow(long long x, long long k, long long m) {
long long res = 1;
while (k) {
if (k & 1) {
res = res * x % m;
}
k /= 2;
x = x * x % m;
}
return res;
}
// check if n is prime
bool check(long long n) {
if (n < 2) {
return false;
}
long long d = n - 1;
long long s = 0;
while (d % 2 == 0) {
d /= 2;
s++;
}
for (long long a : v) {
if (a == n) {
return true;
}
if (modpow(a, d, n) != 1) {
bool ok = true;
for (long long r = 0; r < s; r++) {
if (modpow(a, d * (1LL << r), n) == n - 1) {
ok = false;
break;
}
}
if (ok) {
return false;
}
}
}
return true;
}
};
struct Rho {
std::mt19937 mt;
Miller miller;
long long c;
Rho() {
mt.seed(clock());
}
inline long long f(long long x, long long n) {
return (x * x + c) % n;
}
long long check(long long n) {
if (n == 4) {
return 2;
}
c = mt() % n;
long long x = mt() % n;
long long y = x;
long long d = 1;
while (d == 1) {
x = f(x, n);
y = f(f(y, n), n);
d = std::gcd(abs(x - y), n);
}
if (d == n) {
return -1;
}
return d;
}
std::vector<long long> factor(long long n) {
if (n <= 1) {
return {};
}
if (miller.check(n)) {
return { n };
}
long long res = -1;
while (res == -1) {
res = check(n);
}
std::vector<long long> fa = factor(res);
std::vector<long long> fb = factor(n / res);
fa.insert(fa.end(), fb.begin(), fb.end());
return fa;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
Rho rho;
long long n; cin >> n;
auto v = rho.factor(n);
map<long long, int>mp;
rep(i, v.size()) mp[v[i]]++;
long long ans = 1;
vector<long long>devide = { 1, 1, 2, 3, 5, 7, 11, 15, 22, 30, 42, 56, 77, 101, 135, 176, 231, 297, 385, 490, 627, 792, 1002, 1255, 1575, 1958, 2436, 3010, 3718, 4565, 5604, 6842, 8349, 10143, 12310 };
for (auto[k, v] : mp) ans *= devide[v];
cout << ans << endl;
return 0;
}