結果
問題 | No.826 連絡網 |
ユーザー |
👑 |
提出日時 | 2023-06-29 22:48:49 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,701 ms / 2,000 ms |
コード長 | 764 bytes |
コンパイル時間 | 963 ms |
コンパイル使用メモリ | 85,772 KB |
最終ジャッジ日時 | 2025-02-15 03:10:10 |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 30 |
ソースコード
#include <iostream>#include <vector>#include <set>#include <queue>using namespace std;int main(){int n,p;cin>>n>>p;vector<int> A(n+1);set<int> X;queue<int> Z;Z.push(p);A[p] = 1;while(Z.size()){auto z = Z.front();Z.pop();for(int i = 2; z >= i*i; i++){if(z%i == 0){if(!X.count(i)){X.insert(i);for(int j = i; n >= j; j+=i){A[j] = 1;Z.push(j);}}while(z%i==0)z/=i;}}if(z != 1){if(!X.count(z)){X.insert(z);for(int j = z; n >= j; j+=z){A[j] = 1;Z.push(j);}}}}int ans = 0;for(int i = 0; n >= i; i++){ans += A[i];}cout << ans << endl;}