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