首页 > 技术文章 > codeforces 476C.Dreamoon and Sums 解题报告

windysai 2014-10-24 16:41 原文

题目链接:http://codeforces.com/problemset/problem/476/C

题目意思:给出两个数:a 和 b,要求算出 (x/b) / (x%b) == k,其中 k 的取值范围是 [1, a],找出满足所有正整数的 x 并求出所有 x 的和。

    是不是觉得无从下手呢?我当时也是 = =  .....看了整晚题解,算是看懂了。。。

    首先设 d = x / b,   m = x % b,那么整条式子就变成 d/m = k  —> d = mk(1) (好快你就知道有啥用了)

    这时隐含着一条式子: x = db + m,   很神奇是吧^_^,好戏在后头!

    结合(1)这条式子,推出 x = mkb + m = m(kb+1)

    由于 m 定义的是 x mod b 的余数,那么 m 的取值范围是[0, b-1],又因为分母不为0(题目中有说的,即使不说也是常识,是吧~),所以它最终的范围就是[1, b-1]。此时 x 就为:

    

 

 

    上面的图有点吓人(sigma符号在这里不太好用,好像上下标是写不了数字...),化简后就是 x = b*(b-1)/2 (kb + 1)

    注意这个式子只是针对某个特定 k 而言的!由于 k 的取值范围是[1, a],于是 k 就是 从1 加到 a 的和啦(不画丑陋的图来吓读者了)。最终就变成 

    x = b*(b-1)/2 * ((1+a)*a/2 * b + a)

    (更详细的解题报告在这里:http://codeforces.com/blog/entry/14256,截图如下)

    

   

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstdlib>
 4 #include <cstring>
 5 using namespace std;
 6 
 7 typedef __int64 LL;
 8 const LL MOD = 1e9 + 7;
 9 
10 int main()
11 {
12     LL a, b;
13     while (scanf("%I64d%I64d", &a, &b) != EOF)
14     {
15         LL B = b * (b-1)/2 % MOD;
16         LL A = (1+a) * a / 2 % MOD;
17         LL Ab = (A*b+a) % MOD;
18         LL ans = Ab % MOD * B % MOD;
19         printf("%I64d\n", ans);
20     }
21     return 0;
22 }

 

推荐阅读