格点统计

本文主要是介绍格点统计，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Description

Input

Output

Sample Input

输入1：
3
输入2：
4

Sample Output

输出1：
5

输出2：
8

---

Data Constraint

.
.
.
.
.
.
.
.

分析

这题就是让我们求，在一个坐标系里，有多少个坐标（x,y）相乘小于等于k，即：x*y<=k

---

当k=4时，所求点如下：

观察图，我们可以发现，对于第i行，它的个数是trunc(k/i)，即k div i。
因此，我们可以枚举i(i=1 to k)来求ans，但由于k的数据过大，i=1 to k会超时。
.
.
.
.
让我们再仔细观察图 ：

我们发现，当我们求出第一行时，第一列也会求出来
因此，我们有了一种想法：
枚举i( i=1 to trunc(sqrt(k)) )
每求出一行，就把数量乘2（因为会有重叠的地方，所以要减去重叠的地方再乘2）累加

记得取模

.
.
.
.
.
.
.

程序：

var
k,ans:qword;
i:longint;
beginassign(input,'count.in');reset(input);assign(output,'count.out');rewrite(output);read(k);ans:=0;for i:=1 to trunc(sqrt(k)) doans:=(ans+(trunc(k/i)-(i-1))*2-1) mod 998244353;write(ans);close(input);close(output);
end.

这篇关于格点统计的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---