結果
| 問題 | No.1946 ロッカーの問題 |
| ユーザー |
👑  Nachia
|
| 提出日時 | 2022-05-20 23:26:18 |
| 言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 7 ms / 3,000 ms |
| コード長 | 7,071 bytes |
| コンパイル時間 | 3,819 ms |
| コンパイル使用メモリ | 124,236 KB |
| 最終ジャッジ日時 | 2025-01-29 11:49:17 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 19 |
ソースコード
//// i 人目の生徒が行う操作は、数列で i の約数番目の要素に 1 を足して mod 2 をとることに相当します。// この操作自体は逆方向のゼータ変換で高速にシミュレーションできます。// よって、与えられた状態に対してゼータ変換の逆変換を行えばよいです。// エラトステネスのふるいを用いることで計算量は O(N log log N) になります。//#include <cstdio>#include <string>namespace nachia{const unsigned int INPUT_BUF_SIZE = 2 << 20;const unsigned int OUTPUT_BUF_SIZE = 1 << 20;char input_buf[INPUT_BUF_SIZE];struct input_buf_init{input_buf_init(){input_buf[fread(input_buf, 1, INPUT_BUF_SIZE-1, stdin)] = '\0';}} input_buf_init_instance;struct input_buf_iterator{private:unsigned int p = 0;public:static bool is_whitespace(char ch){switch(ch){case ' ': case '\n': case '\r': case '\t': return true;}return false;}void skip_whitespace(){while(is_whitespace(input_buf[p])) p++;}unsigned int next_uint(){skip_whitespace();unsigned int buf = 0;while(true){char tmp = input_buf[p];if('9' < tmp || tmp < '0') break;buf = buf * 10 + (tmp - '0');p++;}return buf;}int next_int(){skip_whitespace();if(input_buf[p] == '-'){p++;return (int)(-next_uint());}return (int)next_uint();}unsigned long long next_ulong(){skip_whitespace();unsigned long long buf = 0;while(true){char tmp = input_buf[p];if('9' < tmp || tmp < '0') break;buf = buf * 10 + (tmp - '0');p++;}return buf;}long long next_long(){skip_whitespace();if(input_buf[p] == '-'){p++;return (long long)(-next_ulong());}return (long long)next_ulong();}char next_char(){skip_whitespace();return input_buf[p++];}std::string next_token(){skip_whitespace();std::string buf;while(true){char ch = input_buf[p];if(is_whitespace(ch)) break;buf.push_back(ch);p++;}return buf;}};} // namespace nachia#include <vector>#include <algorithm>#include <cassert>#include <iostream>namespace nachia{namespace prime_sieve_explicit_internal{std::vector<bool> isprime = { false }; // a[x] := isprime(2x+1)void CalcIsPrime(int z){if((int)isprime.size() *2+1 < z+1){int new_z = isprime.size();while(new_z*2+1 < z+1) new_z *= 2;z = new_z-1;isprime.resize(z+1, true);for(int i=1; i*(i+1)*2<=z; i++) if(isprime[i]){for(int j=i*(i+1)*2; j<=z; j+=i*2+1) isprime[j] = false;}}}std::vector<int> prime_list = {2};int prime_list_max = 0;void CalcPrimeList(int z){while((int)prime_list.size() < z){if((int)isprime.size() <= prime_list_max + 1) CalcIsPrime(prime_list_max + 1);for(int p=prime_list_max+1; p<(int)isprime.size(); p++){if(isprime[p]) prime_list.push_back(p*2+1);}prime_list_max = isprime.size() - 1;}}void CalcPrimeListUntil(int z){if(prime_list_max < z){CalcIsPrime(z);for(int p=prime_list_max+1; p<(int)isprime.size(); p++){if(isprime[p]) prime_list.push_back(p*2+1);}prime_list_max = isprime.size() - 1;}}}bool IsprimeExplicit(int n){using namespace prime_sieve_explicit_internal;if(n == 2) return true;if(n % 2 == 0) return false;CalcIsPrime(n);return isprime[(n-1)/2];}int NthPrimeExplicit(int n){using namespace prime_sieve_explicit_internal;CalcPrimeList(n);return prime_list[n];}int PrimeCountingExplicit(int n){using namespace prime_sieve_explicit_internal;if(n < 2) return 0;CalcPrimeListUntil(n);auto res = ::std::upper_bound(prime_list.begin(), prime_list.end(), n) - prime_list.begin();return (int)res;}// [l, r)::std::vector<bool> SegmentedSieveExplicit(long long l, long long r){assert(0 <= l); assert(l <= r);long long d = r - l;if(d == 0) return {};::std::vector<bool> res(d, true);for(long long p=2; p*p<=r; p++) if(IsprimeExplicit(p)){long long il = (l+p-1)/p, ir = (r+p-1)/p;if(il <= p) il = p;for(long long i=il; i<ir; i++) res[i*p-l] = false;}if(l < 2) for(long long p=l; p<2 && p<r; p++) res[l-p] = false;return res;}}namespace nachia{template<class Elem>void DivisorZeta(std::vector<Elem>& a){using namespace prime_sieve_explicit_internal;int n = a.size() - 1;for(int d=2; d<=n; d++) if(IsprimeExplicit(d)) for(int i=1; i*d<=n; i++) a[i*d] += a[i];}template<class Elem>void DivisorInvZeta(std::vector<Elem>& a){using namespace prime_sieve_explicit_internal;int n = a.size() - 1;for(int d=2; d<=n; d++) if(IsprimeExplicit(d)) for(int i=n/d; i>=1; i--) a[i] += a[i*d];}template<class Elem>void DivisorMobius(std::vector<Elem>& a){using namespace prime_sieve_explicit_internal;int n = a.size() - 1;for(int d=2; d<=n; d++) if(IsprimeExplicit(d)) for(int i=n/d; i>=1; i--) a[i*d] -= a[i];}template<class Elem>void DivisorInvMobius(std::vector<Elem>& a){using namespace prime_sieve_explicit_internal;int n = a.size() - 1;for(int d=2; d<=n; d++) if(IsprimeExplicit(d)) for(int i=1; i*d<=n; i++) a[i] -= a[i*d];}template<class Elem>std::vector<Elem> GcdConvolution(std::vector<Elem> a, std::vector<Elem> b){assert(a.size() == b.size());assert(1 <= a.size());DivisorInvZeta(a);DivisorInvZeta(b);for(int i=1; i<(int)a.size(); i++) a[i] *= b[i];DivisorInvMobius(a);return a;}template<class Elem>std::vector<Elem> LcmConvolution(std::vector<Elem> a, std::vector<Elem> b){assert(a.size() == b.size());assert(1 <= a.size());DivisorZeta(a);DivisorZeta(b);for(int i=1; i<(int)a.size(); i++) a[i] *= b[i];DivisorMobius(a);return a;}}#include <string>#include <array>#include <atcoder/modint>using namespace std;using i32 = int32_t;using u32 = uint32_t;using i64 = int64_t;using u64 = uint64_t;#define rep(i,n) for(int i=0; i<(int)(n); i++)const i64 INF = 1001001001001001001;using modint = atcoder::static_modint<998244353>;int main(){nachia::input_buf_iterator iitr;int N = iitr.next_uint();int M = iitr.next_uint();vector<int> A(N+1, 0);rep(i,M){ A[iitr.next_uint()] = 1; }nachia::DivisorInvMobius(A);int ans = 0;rep(i,N) if(A[i+1] % 2 == 0) ans++;printf("%d\n", ans);return 0;}