結果

問題 No.3377 Sigma Index × A Problems
コンテスト
ユーザー butsurizuki
提出日時 2025-11-21 23:07:08
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 1,069 ms / 3,000 ms
コード長 1,685 bytes
コンパイル時間 2,820 ms
コンパイル使用メモリ 277,096 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2025-11-21 23:07:17
合計ジャッジ時間 9,116 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 8
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;

using ll=__int128;
const ll mod=998244353;
const ll inv2=499122177;

ll tsum(ll n,ll d){
  n%=mod;
  d%=mod;
  ll res=(n+n*d)%mod;
  res*=d; res%=mod;
  res*=inv2; res%=mod;
  return res;
}

ll rd(){
  long long x;
  cin >> x;
  ll y=x;
  return y;
}

void wt(ll x){
  x%=mod;
  long long y=x;
  cout << y << "\n";
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int t;
  cin >> t;
  while(t>0){
    t--;
    ll n=rd();
    ll g=1;
    ll res=0;
    long long gg=1;
    for(ll i=1;;i++){
      gg=lcm(gg,(long long)i);
      g=gg;
      if(g>n){break;}
      ll lim=(n/g);
      ll uni=(g/i);
      ll whole=min(lim,n/uni);
      // wt(whole);
      // wt(uni);
      res+=whole*uni*n; res%=mod;
      ll sub=(tsum(g,whole)*(uni%mod))%mod;
      // wt(sub);
      res+=(mod-sub); res%=mod;
      res+=whole*uni; res%=mod;
    }
    wt(res);
  }
  return 0;
}

// #include<bits/stdc++.h>

// using namespace std;

// using ll=long long;

// ll f(ll l,ll r){
//   if(l>r){return 0;}
//   set<ll> st;
//   for(ll i=l;i<=r;i++){
//     st.insert(i);
//   }
//   for(ll i=2;;i++){
//     set<ll> und;
//     for(ll j=l;j<=r;j++){
//       if(st.find(i*j)!=st.end()){und.insert(i*j);}
//     }
//     st=und;
//     if(st.empty()){return i-1;}
//   }
// }

// int main(){
//   // ios::sync_with_stdio(false);
//   // cin.tie(nullptr);
//   ll n=1000;
//   for(ll l=1;l<=n;l++){
//     cout << l << " : ";
//     ll pre=0;
//     for(ll r=1;r<=n;r++){
//       ll v=f(l,r);
//       if(pre!=v){
//         cout << "{ " << r << " , " << v << " }, ";
//       }
//       pre=v;
//     }cout << "\n";
//   }
//   return 0;
// }
0