結果
問題 | No.889 素数! |
ユーザー |
![]() |
提出日時 | 2020-07-26 14:26:22 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 164 ms / 2,000 ms |
コード長 | 1,293 bytes |
コンパイル時間 | 1,730 ms |
コンパイル使用メモリ | 167,120 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-06-28 15:03:48 |
合計ジャッジ時間 | 13,469 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 61 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define N (1000000000+7)//#define N 998244353#define INF 1e16typedef long long ll;typedef pair<int,int> P;typedef pair<int,P> Q;const int inf = (int)1e9;ll gcd(ll a, ll b) {if (b > a) {ll tmp = b;b = a;a = tmp;}if (a%b == 0)return b;else return gcd(b, a%b);}ll inv(ll x,ll power) {ll res = 1;ll k = power;ll y = x%N;while (k) {if (k & 1)res = (res*y) % N;y = (y%N*y%N) % N;k /= 2;}return res;}ll d[2000100];bool prime[1000010];void furui() {int i = 2;prime[0]=true;prime[1]=true;while (i <= 1000000) {int j = 2;while (j*j <= i && !prime[i]) {if (i%j == 0) {prime[i] = true;break;}else j++;}int z = 2;while (!prime[i]) {if (i*z <= 1000000) {prime[i*z] = true;z++;}else break;}i++;}}int main(void){furui();int n;cin>>n;if(!prime[n]){cout<<"Sosu!"<<endl;return 0;}for(ll i=2;i*i<=n;i++){if(i*i==n){cout<<"Heihosu!"<<endl;return 0;}}for(ll i=2;i*i*i<=n;i++){if(i*i*i==n){cout<<"Ripposu!"<<endl;return 0;}}ll t = 1;for(ll i=2;i*i<=n;i++){if(n%i==0){ll k = n/i;t+=i+k;}}if(n!=1 && t==n)cout<<"Kanzensu!"<<endl;else cout<<n<<endl;return 0;}