結果
問題 | No.1322 Totient Bound |
ユーザー | maroon_kuri |
提出日時 | 2020-12-28 18:07:47 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 359 ms / 5,000 ms |
コード長 | 10,163 bytes |
コンパイル時間 | 2,843 ms |
コンパイル使用メモリ | 231,268 KB |
実行使用メモリ | 19,104 KB |
最終ジャッジ日時 | 2024-10-03 08:58:31 |
合計ジャッジ時間 | 10,187 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 18 ms
13,108 KB |
testcase_01 | AC | 18 ms
13,112 KB |
testcase_02 | AC | 18 ms
13,108 KB |
testcase_03 | AC | 18 ms
13,108 KB |
testcase_04 | AC | 18 ms
13,108 KB |
testcase_05 | AC | 19 ms
13,108 KB |
testcase_06 | AC | 19 ms
13,104 KB |
testcase_07 | AC | 17 ms
13,112 KB |
testcase_08 | AC | 16 ms
13,108 KB |
testcase_09 | AC | 15 ms
13,108 KB |
testcase_10 | AC | 17 ms
13,108 KB |
testcase_11 | AC | 17 ms
13,108 KB |
testcase_12 | AC | 16 ms
13,108 KB |
testcase_13 | AC | 16 ms
13,108 KB |
testcase_14 | AC | 18 ms
13,052 KB |
testcase_15 | AC | 16 ms
13,104 KB |
testcase_16 | AC | 17 ms
13,108 KB |
testcase_17 | AC | 17 ms
13,112 KB |
testcase_18 | AC | 89 ms
14,520 KB |
testcase_19 | AC | 127 ms
15,388 KB |
testcase_20 | AC | 274 ms
17,828 KB |
testcase_21 | AC | 304 ms
18,208 KB |
testcase_22 | AC | 306 ms
18,208 KB |
testcase_23 | AC | 356 ms
18,976 KB |
testcase_24 | AC | 354 ms
19,100 KB |
testcase_25 | AC | 355 ms
19,104 KB |
testcase_26 | AC | 355 ms
18,972 KB |
testcase_27 | AC | 356 ms
18,976 KB |
testcase_28 | AC | 359 ms
19,104 KB |
testcase_29 | AC | 358 ms
19,100 KB |
testcase_30 | AC | 18 ms
13,108 KB |
testcase_31 | AC | 16 ms
13,104 KB |
testcase_32 | AC | 16 ms
13,104 KB |
testcase_33 | AC | 355 ms
19,104 KB |
testcase_34 | AC | 356 ms
18,976 KB |
testcase_35 | AC | 359 ms
19,104 KB |
testcase_36 | AC | 359 ms
18,976 KB |
testcase_37 | AC | 355 ms
18,980 KB |
testcase_38 | AC | 355 ms
19,100 KB |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll=long long;#define int ll#define rng(i,a,b) for(int i=int(a);i<int(b);i++)#define rep(i,b) rng(i,0,b)#define gnr(i,a,b) for(int i=int(b)-1;i>=int(a);i--)#define per(i,b) gnr(i,0,b)#define pb push_back#define eb emplace_back#define a first#define b second#define bg begin()#define ed end()#define all(x) x.bg,x.ed#define si(x) int(x.size())#ifdef LOCAL#define dmp(x) cerr<<__LINE__<<" "<<#x<<" "<<x<<endl#else#define dmp(x) void(0)#endiftemplate<class t,class u> bool chmax(t&a,u b){if(a<b){a=b;return true;}else return false;}template<class t,class u> bool chmin(t&a,u b){if(b<a){a=b;return true;}else return false;}template<class t> using vc=vector<t>;template<class t> using vvc=vc<vc<t>>;using pi=pair<int,int>;using vi=vc<int>;template<class t,class u>ostream& operator<<(ostream& os,const pair<t,u>& p){return os<<"{"<<p.a<<","<<p.b<<"}";}template<class t> ostream& operator<<(ostream& os,const vc<t>& v){os<<"{";for(auto e:v)os<<e<<",";return os<<"}";}#define mp make_pair#define mt make_tuple#define one(x) memset(x,-1,sizeof(x))#define zero(x) memset(x,0,sizeof(x))#ifdef LOCALvoid dmpr(ostream&os){os<<endl;}template<class T,class... Args>void dmpr(ostream&os,const T&t,const Args&... args){os<<t<<" ";dmpr(os,args...);}#define dmp2(...) dmpr(cerr,__LINE__,##__VA_ARGS__)#else#define dmp2(...) void(0)#endifusing uint=unsigned;using ull=unsigned long long;template<class t,size_t n>ostream& operator<<(ostream&os,const array<t,n>&a){return os<<vc<t>(all(a));}template<int i,class T>void print_tuple(ostream&,const T&){}template<int i,class T,class H,class ...Args>void print_tuple(ostream&os,const T&t){if(i)os<<",";os<<get<i>(t);print_tuple<i+1,T,Args...>(os,t);}template<class ...Args>ostream& operator<<(ostream&os,const tuple<Args...>&t){os<<"{";print_tuple<0,tuple<Args...>,Args...>(os,t);return os<<"}";}template<class t>void print(t x,int suc=1){cout<<x;if(suc==1)cout<<"\n";if(suc==2)cout<<" ";}ll read(){ll i;cin>>i;return i;}vi readvi(int n,int off=0){vi v(n);rep(i,n)v[i]=read()+off;return v;}pi readpi(int off=0){int a,b;cin>>a>>b;return pi(a+off,b+off);}template<class t,class u>void print(const pair<t,u>&p,int suc=1){print(p.a,2);print(p.b,suc);}template<class T>void print(const vector<T>&v,int suc=1){rep(i,v.size())print(v[i],i==int(v.size())-1?suc:2);}string readString(){string s;cin>>s;return s;}template<class T>T sq(const T& t){return t*t;}//#define CAPITALvoid yes(bool ex=true){#ifdef CAPITALcout<<"YES"<<"\n";#elsecout<<"Yes"<<"\n";#endifif(ex)exit(0);#ifdef LOCALcout.flush();#endif}void no(bool ex=true){#ifdef CAPITALcout<<"NO"<<"\n";#elsecout<<"No"<<"\n";#endifif(ex)exit(0);#ifdef LOCALcout.flush();#endif}void possible(bool ex=true){#ifdef CAPITALcout<<"POSSIBLE"<<"\n";#elsecout<<"Possible"<<"\n";#endifif(ex)exit(0);#ifdef LOCALcout.flush();#endif}void impossible(bool ex=true){#ifdef CAPITALcout<<"IMPOSSIBLE"<<"\n";#elsecout<<"Impossible"<<"\n";#endifif(ex)exit(0);#ifdef LOCALcout.flush();#endif}constexpr ll ten(int n){return n==0?1:ten(n-1)*10;}const ll infLL=LLONG_MAX/3;#ifdef intconst int inf=infLL;#elseconst int inf=INT_MAX/2-100;#endifint topbit(signed t){return t==0?-1:31-__builtin_clz(t);}int topbit(ll t){return t==0?-1:63-__builtin_clzll(t);}int botbit(signed a){return a==0?32:__builtin_ctz(a);}int botbit(ll a){return a==0?64:__builtin_ctzll(a);}int popcount(signed t){return __builtin_popcount(t);}int popcount(ll t){return __builtin_popcountll(t);}bool ispow2(int i){return i&&(i&-i)==i;}ll mask(int i){return (ll(1)<<i)-1;}bool inc(int a,int b,int c){return a<=b&&b<=c;}template<class t> void mkuni(vc<t>&v){sort(all(v));v.erase(unique(all(v)),v.ed);}ll rand_int(ll l, ll r) { //[l, r]#ifdef LOCALstatic mt19937_64 gen;#elsestatic mt19937_64 gen(chrono::steady_clock::now().time_since_epoch().count());#endifreturn uniform_int_distribution<ll>(l, r)(gen);}template<class t>void myshuffle(vc<t>&a){rep(i,si(a))swap(a[i],a[rand_int(0,i)]);}template<class t>int lwb(const vc<t>&v,const t&a){return lower_bound(all(v),a)-v.bg;}vvc<int> readGraph(int n,int m){vvc<int> g(n);rep(i,m){int a,b;cin>>a>>b;//sc.read(a,b);a--;b--;g[a].pb(b);g[b].pb(a);}return g;}vvc<int> readTree(int n){return readGraph(n,n-1);}int gcd(int a,int b){return b?gcd(b,a%b):a;}template<class t>t pow_mod(t x,t n,t m){t r=1;while(n){if(n&1)r=(r*x)%m;x=(x*x)%m;n>>=1;}return r;}bool is_prime(ll n) {if (n <= 1) return false;if (n == 2) return true;if (n % 2 == 0) return false;ll d = n - 1;while (d % 2 == 0) d /= 2;for (ll a : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}) {if (n <= a) break;ll t = d;ll y = pow_mod<__int128_t>(a, t, n); // overwhile (t != n - 1 && y != 1 && y != n - 1) {y = __int128_t(y) * y % n; // flowt <<= 1;}if (y != n - 1 && t % 2 == 0) {return false;}}return true;}ll pollard_single(ll n) {auto f = [&](ll x) { return (__int128_t(x) * x + 1) % n; };if (is_prime(n)) return n;if (n % 2 == 0) return 2;ll st = 0;while (true) {st++;ll x = st, y = f(x);while (true) {ll p = gcd((y - x + n), n);if (p == 0 || p == n) break;if (p != 1) return p;x = f(x);y = f(f(y));}}}vc<ll> pollard(ll n) {if (n == 1) return {};ll x = pollard_single(n);if (x == n) return {x};vc<ll> le = pollard(x);vc<ll> ri = pollard(n / x);le.insert(le.end(), ri.begin(), ri.end());return le;}ll primitive_root(ll p) {auto v = pollard(p - 1);//while (true) {// ll g = rand_int(1, p - 1); //[1, p-1]rng(g,4,p){bool ok = true;for (auto d : v) {ll f = (p - 1) / d;if (pow_mod<__int128_t>(g, f, p) == 1) {ok = false;break;}}if (ok) return g;}assert(0);}vc<pi> to_freq(vi a){sort(all(a));vc<pi> res;for(auto v:a){if(res.empty()||res.back().a!=v)res.eb(v,0);res.back().b++;}return res;}vi enum_divs(int n){auto f=to_freq(pollard(n));dmp(f);vi res;auto rec=[&](auto self,int i,int d)->void{if(i==si(f))res.pb(d);else{rep(_,f[i].b+1){self(self,i+1,d);d*=f[i].a;}}};rec(rec,0,1);return res;}const int vmax=ten(6)+10;bool pri[vmax];vi ps;int sf[vmax]; //smallest factor, sf[1] is undefined(0)void linear_sieve(){rng(i,2,vmax)pri[i]=1;rng(i,2,vmax){if(pri[i]){ps.pb(i);sf[i]=i;}for(int j=0;i*ps[j]<vmax;j++){pri[i*ps[j]]=0;sf[i*ps[j]]=ps[j];if(i%ps[j]==0)break;}}}//手元でテストしたら 10^18 まで大丈夫そうだったll isqrt(ll n){return sqrtl(n);}ll icbrt(ll n){return cbrtl(n);}const ull mask64=-1;pair<ull,bool> pow_cap(ull a,int n){if(a==0)return make_pair(0,0);bool over=false;auto mult=[&](ull x,ull y){if(x<=mask64/y)return x*y;else{over=true;return mask64;}};ull res=1;while(n){if(n&1)res=mult(res,a);n>>=1;if(n)a=mult(a,a);}return make_pair(res,over);}//yosupo kth root integer//0<=a<2^64ull kth_root_integer(ull a,int k){if(a==0)return 0;ull z=min((ull)powl(a,(long double)1/k),mask64);while(1){auto w=pow_cap(z,k);if(w.a>a||w.b)z--;else break;}while(z<mask64){auto w=pow_cap(z+1,k);if(w.a<=a&&!w.b)z++;else break;}return z;}//initprime//kth_root_integer//VERIFY:yosupo//pi(n/i) 列挙//sum[i] = pi(vs[i])//O(N^(2/3))//N=10^11, 297ms on yosupo judge//D=int Xmas2019 Dtemplate<class D=int>struct counting_primes{const int n,n2,n3,n6;int s;vi vs,sum,bit;int pre;void trans(int i,int p){int j=getidx(vs[i]/p);sum[i]-=sum[j]-pre;}void trans2(int i,int p){int j=getidx(vs[i]/p);int z=sum[j];if(j>=n3){j-=n3;for(;j<si(bit);j+=(j+1)&(-j-1))z+=bit[j];}sum[i]-=z-pre;}void upd(int i,int cur,bool f){if(!f){for(int x=getidx(cur)-n3;x>=0;x-=(x+1)&(-x-1))bit[x]--;}for(int j=i;cur*ps[j]<=vs[n3];j++)upd(j,cur*ps[j],false);}counting_primes(int nn):n(nn),n2(isqrt(n)),n3(icbrt(n)),n6(kth_root_integer(n,6)){{int v=n;while(v){vs.pb(v);v=n/(n/v+1);}}s=vs.size();sum.resize(s);rep(i,s)sum[i]=vs[i]-1;int idx=0;pre=0;{while(ps[idx]<=n6){rep(i,s){if(sq(ps[idx])>vs[i])break;trans(i,ps[idx]);}pre++;idx++;}}{bit.resize(s-n3);while(ps[idx]<=n3){rep(i,n3){if(sq(ps[idx])>vs[i])break;trans2(i,ps[idx]);}assert(ps[idx]<=vs[n3]);upd(idx,ps[idx],true);pre++;idx++;}per(i,s-n3){int j=i+((i+1)&(-i-1));if(j<si(bit))bit[i]+=bit[j];}rep(i,s-n3){sum[i+n3]+=bit[i];}}{while(ps[idx]<=n2){rep(i,s){if(sq(ps[idx])>vs[i])break;trans(i,ps[idx]);}pre++;idx++;}}}vc<D> buf;D ans;D multiplicative_sum(){buf.resize(s);rep(i,s){buf[i]=sum[i];if(is_prime(vs[i]+1))buf[i]++;}ans=1+buf[0];rep(i,si(ps))if((ps[i])*(ps[i]-1)<=n)dfs(i,n/(ps[i]-1));else break;return ans;}void dfs(int i,int lim){//assert(ps[i]<=lim);ans++;if(lim>=sq(ps[i]))dfs(i,lim/ps[i]);ans+=buf[getidx(lim)]-buf[getidx(ps[i]-1)];for(int j=i+1;(ps[j])*(ps[j]-1)<=lim;j++)dfs(j,lim/(ps[j]-1));}int getidx(int a){return a<=n2?s-a:n/a-1;}};void slv(){int n;cin>>n;counting_primes<int> cp(n);print(cp.multiplicative_sum());}signed main(){cin.tie(0);ios::sync_with_stdio(0);cout<<fixed<<setprecision(20);linear_sieve();//int t;cin>>t;rep(_,t)slv();}