結果

問題 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;
}
0