#define NDEBUG #include #include #include #include #include using namespace std; using i64 = long long; using u64 = unsigned long long; #define rep(i,n) for(i64 i=0; i<(i64)(n); i++) #define repr(i,n) for(i64 i=(i64)(n)-1; i>=0; i--) int main(){ i64 L, N; cin >> L >> N; vector A(N); rep(i,N) cin >> A[i]; vector> pow23(1); pow23[0].push_back(1); while(pow23.back()[0] * 3 <= L){ i64 l = pow23.back()[0]; pow23.emplace_back(1); pow23.back()[0] = l * 3; } for(auto& a : pow23) while(a.back() * 2 <= L) a.push_back(a.back() * 2); int H = (int)max(pow23.size(), pow23[0].size()); vector> coins(H, vector(H)); for(i64 a : A){ int p2 = 0; while(a%2 == 0){ p2++; a /= 2; } int p3 = 0; while(a%3 == 0){ p3++; a /= 3; } coins[p3][p2] = 1; } vector nxrow(H); rep(y,H){ rep(x,H) coins[y][x] ^= nxrow[x]; rep(x,H) if(coins[y][x]){ for(int xx=x+1; xx Q(sz+1); rep(y,H) rep(x,H) if(coins[y][x]) if(y<(int)pow23.size()) if(x<(int)pow23[y].size()){ i64 mp = pow23[y][x]; i64 smallL = L / mp; for(i64 i=1; i*i<=smallL; i++) if(i%2 != 0 && i%3 != 0){ Q[i] += smallL / (i * i); Q[i] -= smallL / (i * i * 2); Q[i] -= smallL / (i * i * 3); Q[i] += smallL / (i * i * 6); } } vector sieve(sz+1, 1); sieve[0] = sieve[1] = 0; vector mobius(sz+1); mobius[1] = 1; for(int p=2; p<=sz; p++) if(sieve[p]){ for(int q=2; p*q<=sz; q++) sieve[p*q] = 0; for(int q=sz/p; q>=1; q--) mobius[p*q] = -mobius[q]; } i64 ans = 0; for(int i=1; i<=sz; i++) ans += Q[i] * mobius[i]; cout << ans << endl; return 0; }