class="markdown_views prism-github-gist"> 题目描述
给一个数整数n,求sum{n%i} (1<=i<=n) (即n%1+n%2+n%3….n%n).
输入
输入由多组数据组成,不超过100组,每组一行.
每行输入一个数n （0 < n <= 10^9）.
到EOF结束；
输出
对于每一个输入的n，输出答案对1000000007取模的值。
样例输入
1
2
3
样例输出
0
0
1
来源
lazier,2014年湖南科技大学校赛
题解
n很大，用常规法肯定会超时，所以想着这里的数据肯定有规律的。
我们先写个程序观察数据， #include using namespace std; int main() { int n=20; int sum=0; for(int i=1;i<=n;i++){ sum+=n%i; printf("%d%%%d=%d ",n,i,n%i); } printf("sum(%d%%i)=%d ",n,sum); return 0; } 通过观察数据（如下图）我们可以看到这样一个特性，n%i的数据的后几次是有规律的，分别呈现几段的单调性（如下图括号标记的）。而每段可以用等差求和公式求出，时间复杂度为O（1）。现在要做的就是找到每段段数据的起始点s，和末端点e来计算该段和。除此之外，当n/i大于等于sqrt(n)的时候，i大约有sqrt（n）大小，而且i的数据没有之前的单调性，只能挨个求，不过总体的时间复杂度却压缩到了O（√n）。 代码 #include #include #include using namespace std; typedef long long LL; int main() { int n; while(~scanf("%d",&n)) { int i,q=sqrt(n),e=n,s; //q为n的平方根，e为结束位置，s为起始位置 LL ans=0; for(i=1;i<=q;i++) { if(n/i>q){ s=n/(i+1)+1; ans=(ans+(LL)(e-s+1)*(n%s+n%e)/2)%1000000007; e=s-1; } ans+=n%i; } printf("%lld ",ans%1000000007); } return 0; } 一份别人分享的代码 #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long LL; template<class T> void read(T &x){bool fu=0;char c;for(c=getchar();c<=32;c=getchar());if(c=='-')fu=1,c=getchar();for(x=0;c>32;c=getchar())x=x*10+c-'0';if(fu)x=-x;}; inline int min_(int a, int b) { return a > b ? b : a; } inline int max_(int a, int b) { return a < b ? b : a; } int N, M; int main() { #ifndef ONLINE_JUDGE freopen("mod_add.in", "r", stdin); freopen("mod_add2.out", "w", stdout); #endif int n; while(cin >> n){ LL ans = 0; int r = (int)sqrt(n + 0.5); for(int i = 2; i <= r; i++){ int beg = n / i + 1; int end = n / (i - 1); if(beg <= end) ans = (ans + (LL)(end - beg + 1) * n - (LL)(i - 1) * (beg + end) * (end - beg + 1) / 2 + n % i ) % 1000000007; } for(int i = r + 1; i <= n / r; i++) ans += n % i; cout << ans % 1000000007 << endl; } return 0; }