codevs月赛第三场4245 Cww的作业

题目描述 Description
师傅给cww布置了道题，cww看到题目就不想写，请你帮忙了：
设n为正整数，令f(n)为所有gcd(x,y)的最大值，且x和y满足$1<=x<y<=n$，其中gcd指最大公约数。
举个例子：当n=3时，x,y可以取1,2或1,3或2,3，gcd(x,y)的最大值为1，因此f(3)=1。
给定正整数m，求当2<=i<=2m+1时，所有f(i)的平方和。
输入描述 Input Description
仅一行，一个正整数m。
输出描述 Output Description
仅一行，所求结果对10007取模的结果。
样例输入 Sample Input
SAMPLE #1:
3
SAMPLE #2:
10
样例输出 Sample Output
SAMPLE #1:
28
SAMPLE #2:
770
数据范围及提示 Data Size & Hint
10% : n ≤ 10.
20% : n ≤ 100.
40% : n ≤ 1000.
60% : n ≤ 10000.
80% : n ≤ 1000000.
100% : n ≤ 10^9.

一道丧心病狂的codevs月赛数学题。先来看f(x)，容易知道$f(x)=\lfloor{x/2}\rfloor$（x严格小于y保证其最大公约数不超过最大值的一半）。那么：
$\displaystyle\sum_{i=2}^{2m+1}{f(x)^2}=1^2+1^2+2^2+2^2+...+m^2+m^2=2*(1^2+2^2+3^2+...+m^2)=2*\frac{m(m+1)(2m+1)}{6}=\frac{m(m+1)(2m+1)}{3}$

#include
using namespace std;
long long n,ans=1;
int main()
{scanf("%lld",&n);if (n%3==0) ans=(ans*n/3)%10007; else ans=(ans*n)%10007;if ((n+1)%3==0) ans=(ans*((n+1)/3)%10007)%10007; else ans=(ans*((n+1))%10007)%10007;if ((2*n+1)%3==0) ans=(ans*((2*n+1)/3)%10007)%10007; else ans=(ans*((2*n+1))%10007)%10007;printf("%lld",ans);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！