結果

問題 No.1396 Giri
ユーザー publfl
提出日時 2021-02-14 21:36:12
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 15 ms / 2,000 ms
コード長 766 bytes
コンパイル時間 536 ms
コンパイル使用メモリ 49,024 KB
実行使用メモリ 7,304 KB
最終ジャッジ日時 2024-07-22 09:00:15
合計ジャッジ時間 1,643 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 23
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <stdio.h>
#include <vector>
#define MOD 998244353
std::vector<int> prime;
int check[1000010];
long long int gcd(long long int a, long long int b)
{
	return a?gcd(b%a,a):b;
}
long long int lcm(long long int a, long long int b)
{
	return (a/gcd(a,b))*b;
}

int main()
{
	for(int i=2;i<=1000000;i++)
	{
		if(check[i]==0)
		{
			prime.push_back(i);
			for(int j=i;j<=1000000;j+=i) check[j] = 1;
		}
	}
	int a;
	scanf("%d",&a);
	
	int t = 0;
	for(int i=prime.size()-1;i>=0;i--)
	{
		if(prime[i]<=a)
		{
			t = prime[i];
			break;
		}
	}
	
	long long int ans = 1;
	for(int i=0;i<prime.size();i++)
	{
		if(prime[i]==t) break;
		long long int C = 1;
		while(1)
		{
			C*=prime[i];
			if(C>a) break;
			ans *= prime[i];
			ans %= MOD;
		}
	}
	printf("%lld\n",ans);
}
0