http://www.codeforces.com/contest/476/problem/C
C. Dreamoon and Sums
Dreamoon loves summing up something for no reason. One day he obtains two integers a and b occasionally. He wants to calculate the sum of all nice integers. Positive integer x is called nice if and , where k is some integer number in range[1, a].
By we denote the quotient of integer division of x and y. By we denote the remainder of integer division of x andy. You can read more about these operations here: http://goo.gl/AcsXhT.
The answer may be large, so please print its remainder modulo 1 000 000 007 (109 + 7). Can you compute it faster than Dreamoon?
The single line of the input contains two integers a, b (1 ≤ a, b ≤ 107).
Print a single integer representing the answer modulo 1 000 000 007 (109 + 7).
1 1
0
2 2
8
For the first sample, there are no nice integers because is always zero.
For the second sample, the set of nice integers is {3, 5}.
题目大意:给你一个公式,输入a和b,对于某满足(x / b) / (x % b) = k(1 <= k <= a),问满足条件的x的总合
思路:我们得到x/b = k * (x%b),令x%b=i,然后枚举i即可得到相应的x = i * k * b + i,
然后即可得到暴力枚举的公式ans = ((1LL * i * ta % mod * b % mod + a * i % mod) % mod + ans) % mod,因此这种方法是O(b)的复杂度( 无语了,这里因为中间的mod爆了LL导致后来卡了一会儿,果然做事需要谨慎点。)
当然如果把i提取出来还可以用O(1)的方法计算。
1 //看看会不会爆int!数组会不会少了一维! 2 //取物问题一定要小心先手胜利的条件 3 #include <bits/stdc++.h> 4 using namespace std; 5 #define LL long long 6 #define ALL(a) a.begin(), a.end() 7 #define pb push_back 8 #define mk make_pair 9 #define fi first 10 #define se second 11 const int maxn = 100 + 5; 12 const LL mod = 1e9 + 7; 13 LL a, b; 14 15 int main(){ 16 cin >> a >> b; 17 LL ans = 0; 18 LL ta = (a + 1) * a / 2 % mod; 19 for (int i = 1; i < b; i++){ 20 ans = ((1LL * i * ta % mod * b % mod + a * i % mod) % mod + ans) % mod; 21 } 22 printf("%I64d ", ans); 23 return 0; 24 }