結果
問題 |
No.1514 Squared Matching
|
ユーザー |
|
提出日時 | 2025-08-27 21:35:28 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
MLE
|
実行時間 | - |
コード長 | 3,454 bytes |
コンパイル時間 | 5,874 ms |
コンパイル使用メモリ | 283,208 KB |
実行使用メモリ | 814,564 KB |
最終ジャッジ日時 | 2025-08-27 21:35:40 |
合計ジャッジ時間 | 7,109 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 1 MLE * 1 -- * 24 |
ソースコード
#include<bits/stdc++.h> #if __has_include(<atcoder/all>) #endif using namespace std; #define eb emplace_back #define LL(...) ll __VA_ARGS__;lin(__VA_ARGS__) #define FO(n) for(ll IJK=n;IJK-->0;) #define fo(i,...) for(auto[i,i##stop,i##step]=for_range<ll>(0,__VA_ARGS__);i<i##stop;i+=i##step) #define of(i,...) for(auto[i,i##stop,i##step]=for_range<ll>(1,__VA_ARGS__);i>=i##stop;i+=i##step) #define fe(a,e,...) for(auto&&__VA_OPT__([)e __VA_OPT__(,__VA_ARGS__]):a) #define defpp template<ostream&o=cout>void pp(const auto&...a){[[maybe_unused]]const char*c="";((o<<c<<a,c=" "),...);o<<'\n';}void epp(const auto&...a){pp<cerr>(a...);} #define entry defpp void main();void main2();}int main(){my::io();my::main();}namespace my{ namespace my{ void io(){cin.tie(nullptr)->sync_with_stdio(0);cout<<fixed<<setprecision(15);} using ll=long long; using ui32=uint32_t; using ui64=uint64_t; using i8=int8_t; template<class T>constexpr auto for_range(T s,T b){T a=0;if(s)swap(a,b);return array{a-s,b,1-s*2};} template<class T>constexpr auto for_range(T s,T a,T b,T c=1){return array{a-s,b,(1-s*2)*c};} void lin(auto&...a){(cin>>...>>a);} constexpr ui64 kth_root_floor(ui64 a,ll k){ if (k==1)return a; auto within=[&](ui32 x){ui64 t=1;FO(k)if(__builtin_mul_overflow(t,x,&t))return false;return t<=a;}; ui64 r=0; of(i,sizeof(ui32)*CHAR_BIT)if(within(r|(1u<<i)))r|=1u<<i; return r; } constexpr auto sqrt_floor(auto x){return kth_root_floor(x,2);} template<class...A>using pack_back_t=tuple_element_t<sizeof...(A)-1,tuple<A...>>; } namespace my{ template<class V>concept vectorial=is_base_of_v<vector<typename remove_cvref_t<V>::value_type>,remove_cvref_t<V>>; template<class V>struct vec; template<int D,class T>struct hvec_helper{using type=vec<typename hvec_helper<D-1,T>::type>;}; template<class T>struct hvec_helper<0,T>{using type=T;}; template<int D,class T>using hvec=hvec_helper<D,T>::type; template<class V>struct vec:vector<V>{ using vector<V>::vector; ll size()const{return vector<V>::size();} auto&emplace_back(auto&&...a){vector<V>::emplace_back(std::forward<decltype(a)>(a)...);return*this;} vec zeta()const{vec v=*this;if constexpr(vectorial<V>){ }fo(i,v.size()-1)v[i+1]+=v[i];return v;} }; template<class...A>requires(sizeof...(A)>=2)vec(const A&...a)->vec<hvec<sizeof...(A)-2,pack_back_t<A...>>>; } namespace my{ ll totient_prime_pow(ll p,i8,ll pk){return(pk-pk/p);} template<class T>struct linear_sieve{ T n; vec<int>lpf; vec<i8>lpf_ord; vec<int>lpf_pow; vec<int>lpf_pow_except; vec<int>primes; linear_sieve(T n):n(n),lpf(n+1,-1),lpf_ord(n+1),lpf_pow(n+1),lpf_pow_except(n+1){ lpf[1]=lpf_ord[1]=lpf_pow[1]=lpf_pow_except[1]=1; fo(i,2,n+1){ if(lpf[i]==-1)primes.eb(lpf[i]=i); fe(primes,p){ if(p*i>n||p>lpf[i])break; lpf[p*i]=p; } int j=i/lpf[i]; lpf_ord[i]=lpf_ord[j]*(lpf[i]==lpf[j])+1; lpf_pow[i]=((lpf_pow[j]-1)*(lpf[i]==lpf[j])+1)*lpf[i]; lpf_pow_except[i]=i/lpf_pow[i]; } } auto multiplicative_function_enumerate(const auto&f)const{ vec<T>r(n+1); r[1]=1; fo(i,2,n+1)r[i]=f(lpf[i],lpf_ord[i],lpf_pow[i])*r[lpf_pow_except[i]]; return r; } auto totient_enumerate()const{return multiplicative_function_enumerate(totient_prime_pow);} }; } namespace my{entry void main(){ LL(N); auto Phi=linear_sieve<int>(N).totient_enumerate().zeta(); ll ans=0; fo(g,1,N+1){ ans+=Phi[sqrt_floor(N/g)]-1; } pp(ans*2+N); }}