Submission #2559821
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define NDEBUG #ifdef DEBUG #include "cout11.h" #undef NDEBUG #endif #include <cassert> typedef long long ll; typedef unsigned long long ull; typedef pair<int,int> ii; typedef pair<ll,ll> llll; typedef pair<double,double> dd; typedef vector<int> vi; typedef vector<vector<int>> vvi; typedef vector<ii> vii; typedef vector<vector<ii>> vvii; typedef vector<ll> vll; #define sz(a) int((a).size()) #define pb push_back #define FOR(var,from,to) for(int var=(from);var<=(to);++var) #define rep(var,n) for(int var=0;var<(n);++var) #define rep1(var,n) for(int var=1;var<=(n);++var) #define repC2(vari,varj,n) for(int vari=0;vari<(n)-1;++vari)for(int varj=vari+1;varj<(n);++varj) #define ALL(c) (c).begin(),(c).end() #define RALL(c) (c).rbegin(),(c).rend() #define tr(i,c) for(auto i=(c).begin(); i!=(c).end(); ++i) #define found(s,e) ((s).find(e)!=(s).end()) #define mset(arr,val) memset(arr,val,sizeof(arr)) #define mid(x,y) ((x)+((y)-(x))/2) #define IN(x,a,b) ((a)<=(x)&&(x)<=(b)) #include <vector> using namespace std; vector<int> primes; vector<int> smallest_prime_factor; int sieve(int nmax){ primes.clear(); smallest_prime_factor.assign(nmax+1, 0); for (int n=2; n<=nmax; ++n) { if (!smallest_prime_factor[n]) { primes.push_back(n); for (int kn=n; kn<=nmax; kn+=n) { if (!smallest_prime_factor[kn]) { smallest_prime_factor[kn] = n; } } } } return primes.size(); } vector<int> factorize(int x) { vector<int> prime_factors; while (x > 1) { int s = smallest_prime_factor[x]; if (!s) break; if (prime_factors.empty() || prime_factors.back() != s) prime_factors.push_back(s); x /= s; } return prime_factors; } int cnt[100001]; inline int _pattern(int num, function<int(int,int)> proc){ vi f = factorize(num); int w = f.size(); int P = 1 << w; int sum = 0; for (int p=1; p<P; ++p) { int x = 1; int pm = -1; for (int b=0,m=1; b<w; ++b,m<<=1) { if (p & m) { x *= f[b]; pm = -pm; } } sum += proc(x,pm); } return sum; } int main() { mset(cnt, 0); sieve(1e5); int N,M; cin >> N >> M; rep(i,N) { int ai; cin >> ai; _pattern(ai, [](int x,int pm){ return ++cnt[x]; }); } rep1(i,M){ int ans = N - _pattern(i, [](int x,int pm){ return cnt[x] * pm; }); cout << ans << endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | A - Uncommon |
User | naoya_t |
Language | C++14 (GCC 5.4.1) |
Score | 600 |
Code Size | 2765 Byte |
Status | AC |
Exec Time | 229 ms |
Memory | 1664 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 600 / 600 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | a01, a02, a03 |
All | a01, a02, a03, b04, b05, b06, b07, b08, b09, b10, b11, b12, b13, b14, b15, b16, b17, b18, b19, b20, b21, b22, b23, b24, b25, b26, b27, b28, b29, b30, b31, b32, b33, b34, b35, b36, b37, b38, b39, b40, b41, b42, b43, b44, b45, b46 |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
a01 | AC | 2 ms | 1152 KB |
a02 | AC | 2 ms | 1152 KB |
a03 | AC | 2 ms | 1152 KB |
b04 | AC | 2 ms | 1152 KB |
b05 | AC | 178 ms | 1280 KB |
b06 | AC | 48 ms | 1152 KB |
b07 | AC | 229 ms | 1664 KB |
b08 | AC | 227 ms | 1664 KB |
b09 | AC | 182 ms | 1664 KB |
b10 | AC | 186 ms | 1664 KB |
b11 | AC | 192 ms | 1664 KB |
b12 | AC | 196 ms | 1664 KB |
b13 | AC | 207 ms | 1664 KB |
b14 | AC | 208 ms | 1664 KB |
b15 | AC | 213 ms | 1664 KB |
b16 | AC | 215 ms | 1664 KB |
b17 | AC | 221 ms | 1664 KB |
b18 | AC | 225 ms | 1664 KB |
b19 | AC | 225 ms | 1664 KB |
b20 | AC | 226 ms | 1664 KB |
b21 | AC | 226 ms | 1664 KB |
b22 | AC | 228 ms | 1664 KB |
b23 | AC | 203 ms | 1664 KB |
b24 | AC | 203 ms | 1664 KB |
b25 | AC | 186 ms | 1664 KB |
b26 | AC | 208 ms | 1664 KB |
b27 | AC | 224 ms | 1664 KB |
b28 | AC | 182 ms | 1536 KB |
b29 | AC | 190 ms | 1664 KB |
b30 | AC | 191 ms | 1664 KB |
b31 | AC | 198 ms | 1664 KB |
b32 | AC | 199 ms | 1664 KB |
b33 | AC | 207 ms | 1664 KB |
b34 | AC | 212 ms | 1664 KB |
b35 | AC | 212 ms | 1664 KB |
b36 | AC | 216 ms | 1664 KB |
b37 | AC | 219 ms | 1664 KB |
b38 | AC | 223 ms | 1664 KB |
b39 | AC | 195 ms | 1664 KB |
b40 | AC | 200 ms | 1664 KB |
b41 | AC | 202 ms | 1664 KB |
b42 | AC | 213 ms | 1664 KB |
b43 | AC | 222 ms | 1664 KB |
b44 | AC | 37 ms | 1152 KB |
b45 | AC | 14 ms | 1152 KB |
b46 | AC | 27 ms | 1152 KB |