結果
問題 | No.7 プライムナンバーゲーム |
ユーザー |
![]() |
提出日時 | 2014-10-26 16:10:31 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 25 ms / 5,000 ms |
コード長 | 1,991 bytes |
コンパイル時間 | 725 ms |
コンパイル使用メモリ | 89,344 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-10-01 15:27:22 |
合計ジャッジ時間 | 1,496 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 17 |
ソースコード
#include<iostream> #include <fstream> #include <stdio.h> #include <stdlib.h> #define _USE_MATH_DEFINES #include <math.h> #include<string> #include<vector> #include<cmath> #include<stack> #include<queue> #include<sstream> #include<algorithm> #include<map> #include<complex> #include<ctime> #include<set> using namespace std; #define li long long int #define rep(i,to) for(li i=0;i<((li)(to));i++) #define repp(i,start,to) for(li i=(li)(start);i<((li)(to));i++) #define pb push_back #define sz(v) ((li)(v).size()) #define bgn(v) ((v).begin()) #define eend(v) ((v).end()) #define allof(v) (v).begin(), (v).end() #define dodp(v,n) memset(v,(li)n,sizeof(v)) #define bit(n) (1ll<<(li)(n)) #define mp(a,b) make_pair(a,b) #define rin rep(i,n) #define EPS 1e-10 #define ETOL 1e-8 #define MOD 1000000007 #define F first #define S second #define p2(a,b) cout<<a<<"\t"<<b<<endl #define p3(a,b,c) cout<<a<<"\t"<<b<<"\t"<<c<<endl li prime[10001]; vector<li> primes; vector<pair<li,li> > prime_decomposition(li x){ vector<pair<li,li> > res; rep(i,sz(primes)){ li cnt=0; while(x%primes[i]==0){ x/=primes[i]; cnt++; } if(cnt>0)res.pb(mp(primes[i], cnt)); } if(x!=1)res.pb(mp(x, 1)); return res; } li dp[10001][2]; int main(){ rep(i,10001)prime[i]=true; prime[0]=prime[1]=false; repp(i,2,1100){ if(prime[i]) for(li j=2; i*j<10001; j++){ prime[i*j]=false; } } rep(i,10001)if(prime[i])primes.pb(i); li n; cin>>n; //cout<<sz(primes)<<endl; dp[0][0]=dp[1][0]=0; dp[0][1]=dp[1][1]=1; repp(i,2,n+1){ dp[i][0]=0; dp[i][1]=1; rep(j,sz(primes)){ if(primes[j]>i)break; if(i-primes[j]<2){ ; } else{ if(dp[i-primes[j]][1]==1)dp[i][0]=1; if(dp[i-primes[j]][0]==0)dp[i][1]=0; } } } //rep(i,n+1)cout<<dp[i][0]<<" ";puts(""); //rep(i,n+1)cout<<dp[i][1]<<" ";puts(""); cout<<(dp[n][0]>0 ? "Win" : "Lose")<<endl; return 0; }