結果
問題 | No.144 エラトステネスのざる |
ユーザー |
![]() |
提出日時 | 2015-02-06 00:28:00 |
言語 | C++11(廃止可能性あり) (gcc 13.3.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,079 bytes |
コンパイル時間 | 1,236 ms |
コンパイル使用メモリ | 75,616 KB |
実行使用メモリ | 31,440 KB |
最終ジャッジ日時 | 2024-06-23 09:07:08 |
合計ジャッジ時間 | 2,170 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 9 WA * 8 |
ソースコード
#include <iostream> #include <algorithm> #include <vector> #include <string> #include <map> #include <set> #include <cmath> #define FOR(i,a,b) for (int i=(a);i<(b);i++) #define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--) #define REP(i,n) for (int i=0;i<(n);i++) #define RREP(i,n) for (int i=(n)-1;i>=0;i--) #define PB push_back #define ALL(a) (a).begin(),(a).end() #define PII pair<int,int> #define VS vector<string> #define VD vector<double> #define VL vector<long> #define V(type) vector<type> #define DEBUG(x) cout<<#x<<": "<<x<<endl using namespace std; VD Eratosthenes(int n, double p, double& result_p){ VD koho, dst; FOR(i, 2, n+1){ koho.push_back(i); } VD backup_koho = koho; if ( p != 1.0 ){ REP(i, koho.size()){ dst.push_back(koho[i]); int j = 0; // if ( koho[i] > 1 ){ double piv = backup_koho[i]; while ( i + j * piv <= koho.size() - 1 ) { if ( koho[i + j * piv] >= 1 ) { koho[i + j * piv] = p; ++j; continue; } koho[i + j * piv] *= p; ++j; } // } } } else { REP(i, koho.size()){ dst.push_back(koho[i]); int j = 0; if ( koho[i] > 1 ){ double piv = backup_koho[i]; while ( i + j * piv <= koho.size() - 1 ) { koho[i + j * piv] = 0; ++j; } // } } } } return dst; } int main(int argc, const char * argv[]) { int N; double P; VD result; double result_p = 0; cin >> N >> P; result = Eratosthenes(N, P, result_p); // cout << result_p << endl; double sum = 0; FOR(i, 0, result.size()){ if ( result[i] >= 1 ){ sum++; } else { sum += result[i]; } } if ( P == 0 ){ cout << result.size() << endl; } else { cout << sum << endl; } return 0; }