結果
問題 | No.144 エラトステネスのざる |
ユーザー |
![]() |
提出日時 | 2018-01-21 20:35:56 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
RE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 3,477 bytes |
コンパイル時間 | 913 ms |
コンパイル使用メモリ | 96,276 KB |
実行使用メモリ | 11,468 KB |
最終ジャッジ日時 | 2024-12-25 21:53:57 |
合計ジャッジ時間 | 5,688 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | RE * 3 |
other | RE * 17 |
コンパイルメッセージ
main.cpp: In function 'int sieve(int)': main.cpp:88:1: warning: no return statement in function returning non-void [-Wreturn-type] 88 | } | ^ main.cpp: In function 'int zaru(int)': main.cpp:105:1: warning: no return statement in function returning non-void [-Wreturn-type] 105 | } | ^
ソースコード
#include <vector>#include <list>#include <map>#include <set>#include <deque>#include <stack>#include <bitset>#include <algorithm>#include <functional>#include <numeric>#include <utility>#include <sstream>#include <iostream>#include <iomanip>#include <cstdio>#include <cmath>#include <cstdlib>#include <cctype>#include <string>#include <cstring>#include <ctime>#include <queue>using namespace std;//conversion//------------------------------------------inline int toInt(string s) {int v; istringstream sin(s);sin>>v;return v;}template<class T> inline string toString(T x) {ostringstream sout;sout<<x;return sout.str();}//math//-------------------------------------------template<class T> inline T sqr(T x) {return x*x;}//typedef//------------------------------------------typedef vector<int> VI;typedef vector<VI> VVI;typedef vector<string> VS;typedef pair<int, int> PII;typedef long long LL;//container util//------------------------------------------#define ALL(a) (a).begin(),(a).end()#define RALL(a) (a).rbegin(), (a).rend()#define PB push_back#define MP make_pair#define SZ(a) int((a).size())#define EACH(i,c) for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); ++i)#define EXIST(s,e) ((s).find(e)!=(s).end())#define SORT(c) sort((c).begin(),(c).end())//repetition//------------------------------------------#define FOR(i,a,b) for(int i=(a);i<(b);++i)#define REP(i,n) FOR(i,0,n)//constant//--------------------------------------------const double EPS = 1e-10;const double PI = acos(-1.0);//clear memory#define CLR(a) memset((a), 0 ,sizeof(a))//debug#define dump(x) cerr << #x << '=' << (x) << endl;#define debug(x) cerr << #x << '=' << (x) << '('<<'L' << __LINE__ << ')' << ' ' << __FILE__ << endl;const int MAX_N=1234567;int prime[MAX_N];bool is_prime[MAX_N+1];int pownum[MAX_N];int num=0;//エラトステネスのふるいint sieve(int n){REP(i,MAX_N){is_prime[i]=true;}is_prime[0]=is_prime[1]=false;for(int i=2;i<=n;i++){if(is_prime[i]){prime[num++]=i;for(int j=2*i;j<=n;j+=i){is_prime[j]=false;//pownum[j]++;}}}}//ざるint primez[MAX_N];bool is_primez[MAX_N+1];int num2=0;int zaru(int n){REP(i,MAX_N){is_primez[i]=true;}is_primez[0]=is_primez[1]=false;for(int i=2;i<=n;i++){if(is_primez[i]){primez[num++]=i;for(int j=2*i;j<=n;j+=i){//is_prime[j]=false;pownum[j]++;}}}}int main(){int N;double p;cin>>N>>p;sieve(N);zaru(N);double ans=0.0;for(int i=2;i<=N;i++){if(is_prime[i]){//cerr<<i<<" prime"<<endl;ans+=1.0;}else{// int pow_=0;// //約数の個数だけ見ればよい// int i2=i;// for(int j=2;j*j<=i;j++){// // if(i%j==0){// // pow_++;// // }// while(i2%j==0){// pow_++;// if(i2/j!=i2){// pow_++;// }// i2/=j;// }// }//cerr<<i<<" "<<pownum[i]<<endl;ans+=pow((1-p),pownum[i]);}}cout<<fixed<<setprecision(28)<<ans<<endl;}