結果

問題 No.1781 LCM
ユーザー karinohitokarinohito
提出日時 2024-11-10 05:43:35
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 2,783 bytes
コンパイル時間 3,544 ms
コンパイル使用メモリ 228,912 KB
実行使用メモリ 59,424 KB
最終ジャッジ日時 2024-11-10 05:43:49
合計ジャッジ時間 11,319 ms
ジャッジサーバーID
(参考情報)
judge1 / judge4
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 12 ms
11,520 KB
testcase_01 AC 16 ms
11,648 KB
testcase_02 AC 16 ms
11,648 KB
testcase_03 AC 15 ms
11,648 KB
testcase_04 AC 15 ms
11,648 KB
testcase_05 AC 16 ms
11,648 KB
testcase_06 AC 16 ms
11,648 KB
testcase_07 AC 13 ms
11,520 KB
testcase_08 AC 12 ms
11,520 KB
testcase_09 AC 13 ms
11,520 KB
testcase_10 AC 13 ms
11,648 KB
testcase_11 AC 12 ms
11,520 KB
testcase_12 AC 12 ms
11,520 KB
testcase_13 AC 14 ms
11,648 KB
testcase_14 AC 13 ms
11,520 KB
testcase_15 AC 13 ms
11,520 KB
testcase_16 AC 14 ms
11,520 KB
testcase_17 AC 14 ms
11,648 KB
testcase_18 AC 14 ms
11,648 KB
testcase_19 AC 13 ms
11,520 KB
testcase_20 AC 13 ms
11,520 KB
testcase_21 TLE -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include<bits/stdc++.h>
using namespace std;
#include<atcoder/modint>
using namespace atcoder;
using mint=modint998244353;
using ll = long long;
vector<bool> is_prime;
vector<ll> Q_enum;
vector<vector<int>> POW;
unordered_map<ll,ll> ID;
vector<ll> DI;
void enum_prime(ll N){
ll sq=sqrt(N);
POW.resize(sq+1);
is_prime.assign(sq+1,1);
is_prime[0]=is_prime[1]=0;
for(ll i=0;i<=sq;i++){
if(is_prime[i]){
for(ll j=i*2;j<=sq;j+=i)is_prime[j]=0;
ll r=1;
int s=0;
while(r<=N){
s+=(r%3);
POW[i].push_back(s%3);
r*=i;
}
}
}
return;
}
void calc_Qenum(ll N){
ll sq=sqrt(N);
for(int i=1;i<=sq;i++){
Q_enum.emplace_back(N/i);
ID[N/i]=ID.size();
DI.push_back(N/i);
}
while(Q_enum.back()>1){
ID[Q_enum.back()-1]=ID.size();
DI.push_back(Q_enum.back()-1);
Q_enum.emplace_back(Q_enum.back()-1);
}
return;
}
ll A,B;
mint sum_n(ll n,ll c){
if(c==1){
return (n+2)/3-1;
}
if(c==2)return (n+1)/3;
else if(c==0)return n/3;
return 1;
}
vector<mint> calc_Fprime(ll N){
ll sq=sqrt(N);
int sz=Q_enum.size();
vector<mint> F_pr(sz);
for(int j=0;j<sz;j++){
F_pr[j]=DI[j]-1;
}
for(ll x=2;x<=sq;x++){
if(is_prime[x]){
for(int j=0;j<sz;j++){
ll n=Q_enum[j];
if(n<x*x)break;
int u=ID[n/x];
int y=ID[x-1];
F_pr[j]-=mint(F_pr[u]-F_pr[y]);
}
}
}
return F_pr;
}
vector<mint> INV(100,1);
//f(p^e)
auto g_calc=[](ll p,ll e){
return INV[e+1];
};
vector<mint> Min_sieve(ll N,function<mint(ll,ll)> fn,vector<mint> F_pr){
int sz=Q_enum.size();
vector<mint> L_DP(sz);
for(int i=0;i<sz;i++)L_DP[i]=F_pr[i];
ll sq=sqrt(N);
for(ll x=sq;x>1;x--){
if(is_prime[x]){
for(int i=0;i<sz;i++){
ll n=Q_enum[i];
if(n<x*x)break;
ll cnt=1;
int y=ID[x];
for(ll c=x;c*x<=n;c*=x){
L_DP[i]+=fn(x,cnt)*(L_DP[ID[n/c]]-F_pr[y])+fn(x,cnt+1);
cnt++;
}
}
}
}
return L_DP;
}
void solve(){
ll N,M;
cin>>N>>M;
swap(N,M);
for(int i=1;i<100;i++){
INV[i]=mint(i).pow(M);
}
Q_enum.clear();
ID.clear();
DI.clear();
calc_Qenum(N);
vector<mint> FP=calc_Fprime(N);
for(auto &p:FP)p*=INV[2];
vector<mint> G_DP=Min_sieve(N,g_calc,FP);
cout<<(G_DP[ID[N]]+1).val()<<endl;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
enum_prime(1e11+1);
solve();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0