=∑i∑j((n mod i)(m mod j))∑i∑j(n−⌊ni⌋i)(m−⌊mj⌋j)−∑i(n−⌊ni⌋i)(m−⌊mi⌋i)
%%% http://blog.csdn.net/acdreamers/article/details/8809517 #include #include using namespace std; typedef long long ll; ll read() { ll s = 0, f = 1; char ch = getchar(); for (; ch < '0' || ch > '9'; ch = getchar()) if (ch == '-') f = -1; for (; '0' <= ch && ch <= '9'; ch = getchar()) s = s * 10 + ch - '0'; return s * f; } const ll mod = 19940417; ll n, m, ans; ll sum(ll n) { return n * (n + 1) % mod * (2 * n + 1) % mod * 3323403 % mod; } ll solve(ll m, ll n) { ll ans = 0, i, p; for (i = 1; i <= m; i = p + 1) { p = min(m, n / (n / i)); (ans += (n / i) * (i + p) % mod * (p - i + 1) % mod * 9970209 % mod) %= mod; } return ans; } int main() { ll n = read(), m = read(), i, ans, p; if (n < m) swap(n, m); ans = (n * n - solve(n, n)) % mod * ((m * m - solve(m, m)) % mod); (ans += -m * m % mod * n % mod + solve(m, n) * m % mod + solve(m, m) * n % mod) %= mod; for (i = 1; i <= m; i = p + 1) { p = min(m, min(n / (n / i), m / (m / i))); (ans += -(n / i) * (m / i) % mod * ((sum(p) - sum(i - 1)) % mod) % mod) %= mod; } printf("%lld ", (ans % mod + mod) % mod); return 0; }

2956: 模积和

Time Limit: 10 Sec Memory Limit: 128 MB
Submit: 1000 Solved: 430

Description

∑∑((n mod i)(m mod j))
其中1≤i≤n,1≤j≤m,i≠j。
　　

Input

第一行两个数n,m。

Output

　　一个整数表示答案mod 19940417的值

Sample Input

3 4

Sample Output

1

样例说明

　　答案为(3 mod 1)(4 mod 2)+(3 mod 1) (4 mod 3)+(3 mod 1) * (4 mod 4) + (3 mod 2) * (4 mod 1) + (3 mod 2) * (4 mod 3) + (3 mod 2) * (4 mod 4) + (3 mod 3) * (4 mod 1) + (3 mod 3) * (4 mod 2) + (3 mod 3) * (4 mod 4) = 1

数据规模和约定

　　对于100%的数据n,m<=10^9。