結果

問題 No.3607 Sum of Powers of GCDs
コンテスト
ユーザー askr58
提出日時 2026-07-31 22:07:34
言語 C++23
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 629 ms / 2,500 ms
+ 962µs
コード長 974 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,191 ms
コンパイル使用メモリ 189,372 KB
実行使用メモリ 93,280 KB
最終ジャッジ日時 2026-07-31 22:07:43
合計ジャッジ時間 8,420 ms
ジャッジサーバーID
（参考情報） 		judge2_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <iostream>
#include <ranges>
#include <algorithm>
#include <vector>
#include <atcoder/modint>
using mint=atcoder::modint998244353;
using namespace std;
using ll=long long;
int main(){
	cin.tie(nullptr);
	ios::sync_with_stdio(false);
	int ttt;
	cin>>ttt;
	int maxm=1000000;
	vector<vector<mint>> f(11,vector<mint>(maxm+1));
	vector<vector<mint>> fsum(11,vector<mint>(maxm+2));
	for(int i=1;i<=10;i++){
		f[i][1]=1;
		fsum[i][2]=1;
		for(int j=2;j<=maxm;j++){
			f[i][j]+=((mint)j).pow(i)-1;
			for(int l=j+j;l<=maxm;l+=j)f[i][l]-=f[i][j];
			fsum[i][j+1]=fsum[i][j]+f[i][j];
		}
	}
	while(ttt--){
		int n,m,k;
		cin>>n>>m>>k;
		vector<int> v;
		int t=1;
		while(t<=m){
			v.push_back(m/t);
			t=(m/(m/t))+1;
		}
		mint ans=0;
		//for(int i=1;i<=m;i++)cout<<f[k][i].val()<<" ";
		//cout<<endl;
		for(int x:v){
			int l=m/(x+1)+1;
			int r=m/x+1;
			//cout<<x<<" "<<l<<" "<<r<<endl;
			ans+=(fsum[k][r]-fsum[k][l])*((mint)x).pow(n);
		}
		cout<<ans.val()<<endl;

	}
}
0