Problem 2970 --Function

2970: Function

上一题 正确率: $66.67\%$ 下一题
"
Time Limit $5$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $9$ 正确数量 $6$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签

Description

Jerry is fond of functions. He thinks the mystery of the universe is hidden behind the notations, variables and numbers. 
Of all functions, he thinks gcdgcd and ⌊x⌋⌊x⌋ are the most fascinating, and that something combines gcd with truncation should be even more marvelous. 
Therefore, he comes up with a problem: calculate 
∑ni=1gcd(⌊i√3⌋,i)mod998244353

Input

The input contains several test cases. 
The first line contains an integer T(1≤T≤11)T(1≤T≤11), the number of test cases. 
Each of the next TT lines contains a integer n(1≤n≤1021)n(1≤n≤1021), indicating a query.

Output

For each test case, output one line containing an integer indicating the corresponding answer.

Sample Input复制

10
64
180
526
267
775
649
749
908
300
255

Sample Output复制

103
327
1069
522
1693
1379
1631
1998
606
492

提示

g++ compiler on HDOJ supports __int128. And you may need the following function:
[pre]
template <class T>
void read(T &x) {
	static char ch;static bool neg;
	for(ch=neg=0;ch<'0' || '9'<ch;neg|=ch=='-',ch=getchar());
	for(x=0;'0'<=ch && ch<='9';(x*=10)+=ch-'0',ch=getchar());
	x=neg?-x:x;
}
[/pre]

推荐代码 查看2970 所有题解 上传题解视频得图灵币

本题记录 用 户（点击查看用户） 运行号（点击购买题解） 时 间
算法最快[$1586 $ms] 刘成健 461299 2019-09-06 17:10:23
内存最少[$89100 $KB] Camel 902900 2022-10-15 14:25:11
第一AC 刘成健 461299 2019-09-06 17:10:23
第一挑战 刘成健 461299 2019-09-06 17:10:23

赛题来源/所属竞赛 2019 Multi-University Training Contest 1 N/A

竞赛编号 竞赛名称 竞赛时间 访问比赛