結果

問題 No.487 2017 Calculation(2017の計算)
ユーザー bal4u
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

// yukicoder: No.487 2017 Calculation(2017)
// 2019.4.16 bal4u
// 2017^phi(M) = 1 ( mod M )
#include <stdio.h>
#define MAX 2017
#define SIZE 25
int 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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0