結果
問題 |
No.826 連絡網
|
ユーザー |
|
提出日時 | 2019-05-03 22:11:44 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 5 ms / 2,000 ms |
コード長 | 1,196 bytes |
コンパイル時間 | 528 ms |
コンパイル使用メモリ | 72,144 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-11-24 02:24:40 |
合計ジャッジ時間 | 1,496 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
#include<iostream> #include<string> #include<iomanip> #include<cmath> #include<vector> #include<algorithm> using namespace std; #define int long long #define rep(i,n) for(int i = 0; i < (n); i++) #define INF ((long long)1e18) #define MOD ((int)1e9+7) #define endl "\n" #define yn(f) ((f)?"Yes":"No") #define YN(f) ((f)?"YES":"NO") #define MAX #define MAX_PN 1010000 bool PN[MAX_PN]; void huga(int t, int x){ if(PN[t]) return; for(int i = t*t; i <= x; i+=t) PN[i] = true; } void Sieve_of_Eratosthenes(int x){ PN[0]=PN[1]=PN[4]=true; for(int i = 6; (i-1)*(i-1) <= x; i+=6) huga(i-1,x),huga(i+1,x); for(int i = 6; i <= x; i+=6) PN[i]=PN[i+2]=PN[i+3]=PN[i+4]=true; } signed main(){ cin.tie(0); ios::sync_with_stdio(false); cout<<fixed<<setprecision(10); int N, P; int ans = 0, con = 0; cin>>N>>P; Sieve_of_Eratosthenes(N+1); for(int i = N/2 + 1; i <= N; i++){ if(PN[i] == true) con++; // cout<<"i = "<<i<<endl; } // cout<<N/2 - 1<<" "<<con<<sendl; con = N/2 - 1 + con; if(P == 1){ cout<<1<<endl; } else if(P <= N/2){ cout<<con<<endl; } else if(PN[P] == true){ cout<<con<<endl; } else if(PN[P] == false){ cout<<1<<endl; } return 0; }