結果
問題 | No.1255 ハイレーツ・オブ・ボリビアン |
ユーザー |
👑 ![]() |
提出日時 | 2020-08-17 00:26:12 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,804 bytes |
コンパイル時間 | 667 ms |
コンパイル使用メモリ | 71,540 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-28 05:39:47 |
合計ジャッジ時間 | 1,220 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 1 |
other | WA * 15 |
ソースコード
#include<iostream>#include<vector>#include <algorithm>using namespace std;vector<pair<long long,long long>> Prime_Factorization(long long n) {vector<pair<long long,long long>> v;if (n == 1) {v.push_back(make_pair(1, 1));return v;}long long k = 2;while (k * k <= n) {if (n % k == 0) {long c = 0;while (n % k == 0) {c++;n /= k;}v.push_back(make_pair(k, c));}k++;}if (n != 1) {v.push_back(make_pair(n, 1));}return v;}long long power(long long a, long long n) {long long ans = 1;long long x = a;while (n > 0) {if (n % 2 == 1) {ans *= x;}x *= x;n /= 2;}return ans;}long long power_mod(long long a, long long n, long long m) {long long ans = 1;long long x = a % m;while (n > 0) {if (n % 2 == 1) {ans = (ans * x) % m;}x = (x * x) % m;n /= 2;}return ans;}long long Euler_Totient(long long n) {if (n == 1) {return 1;}vector<pair<long long, long long>> p;p = Prime_Factorization(n);long long R = 1;for (int i = 0; i < p.size(); i++) {R *= power(p.at(i).first, p.at(i).second - 1) * (p.at(i).first - 1);}return R;}vector<long long> Divisors(long long n) {vector<long long> u, v;long long k = 1;while (k * k <= n) {if (n % k == 0) {u.push_back(k);if (k != n / k) {v.push_back(n / k);}}k++;}reverse(begin(v), end(v));u.insert(u.end(), v.begin(), v.end());return u;}int main() {long long a = 1;long long ans = 0;long long N;cin >> N;long long M = 2 * N - 1;long long phi = Euler_Totient(M);vector<long long> v = Divisors(phi);reverse(begin(v), end(v));for (int i = 0; i < v.size(); i++) {if ((power_mod(2, v.at(i), M) - 1) % M == 0) {ans = v.at(i);}}cout << ans << endl;}