結果
問題 | No.487 2017 Calculation(2017の計算) |
ユーザー |
![]() |
提出日時 | 2019-04-16 22:34:46 |
言語 | C (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 1 ms / 2,000 ms |
コード長 | 1,055 bytes |
コンパイル時間 | 206 ms |
コンパイル使用メモリ | 30,208 KB |
実行使用メモリ | 6,948 KB |
最終ジャッジ日時 | 2024-09-22 08:24:25 |
合計ジャッジ時間 | 886 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 16 |
ソースコード
// yukicoder: No.487 2017 Calculation(2017の計算)// 2019.4.16 bal4u// 2017^phi(M) = 1 ( mod M )#include <stdio.h>#define MAX 2017#define SIZE 25int factor[SIZE]; int size;int ptbl[] = { 3,5,7,11,13,17,19,23,29,31,37,41,43,0 };void prime_factor(int n){int d, *pp;size = 0;if ((n & 1) == 0) {factor[size++] = 2;do n >>= 1;while ((n & 1) == 0);}for (pp = ptbl; n > 1 && *pp > 0; pp++) {if (n % *pp) continue;d = *pp, factor[size++] = d;do n /= d;while (n % d == 0);}if (n > 1) factor[size++] = n;}int euler_phi(int n){int i, ans;prime_factor(n);ans = n; for (i = 0; i < size; i++) ans = (ans/factor[i])*(factor[i]-1);return ans;}int bigPow(int x, int p, int mod){int r = 1;while (p) {if (p & 1) r = (long long)r * x % mod;x = (long long)x * x % mod;p >>= 1;}return r;}int main(){int a, M, ans;scanf("%d", &M);if (M == 1 || M == 2017) ans = 0;else {a = euler_phi(M);ans = (2017 % M + bigPow(2017, 4034 % a, M)) % M;}printf("%d\n", ans);return 0;}