#include //#include using namespace std; //using namespace atcoder; using ll = long long; //using mint = modint998244353; struct Erat{ vector spf; vector prime_table; vector mobius; Erat(int m){ assert(m <= 10000000); spf.resize(m+1, -1); prime_table.resize(m+1, 1); mobius.resize(m+1, 1); prime_table[0] = 0; prime_table[1] = 0; spf[1] = 1; for (int i=2; i<=m; i++){ if (prime_table[i]){ spf[i] = i; mobius[i] = -1; for (int j=i*2; j<=m; j+=i){ prime_table[j] = 0; if (spf[j] == -1) spf[j] = i; if ((j/i) % i == 0) mobius[j] = 0; else mobius[j] = -mobius[j]; } } } } map prime_factor(int n) const{ map res; while(n != 1){ res[spf[n]]++; n /= spf[n]; } return res; } vector all_factor(int n) const{ vector res={1}; map prime = prime_factor(n); for (auto [p, e] : prime){ int x=1, m=res.size(); for (int j=0; j vector fast_zeta(const vector &vec) const{ int n = vec.size(); vector res=vec; for (int i=2; i=1; j--) res[j] += res[j*i]; } return res; } template vector fast_mobius(const vector &vec) const{ int n = vec.size(); vector res=vec; for (int i=2; i vector gcd_convolution(const vector & _f, const vector & _g){ vector f=_f, g=_g, h; int n = max(f.size(), g.size()); f.resize(n); g.resize(n); h.resize(n); f = fast_zeta(f); g = fast_zeta(g); for (int i=1; i> N; Erat erat(100000); for (int p=1; p<=100000; p++){ if (erat.is_prime(p)){ ll pw=(ll)p*p; while(pw<=N){ ans += pw; pw *= p; } } } cout << ans << endl; return 0; }