「CF477A」Dreamoon and Sums
Dreamoon loves summing up something for no reason. One day he obtains two integers aand 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 and y. 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 1 |
|
1 |
|
1 |
2 2 |
|
1 |
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}.
题解
求 ∑ x （div ( x , b) / mod ( x , b ) = k && 1<=k<=a）
设 m = mod ( x , b ) 则 x = m * k * b + m
1 <= m <= b – 1
则 ∑ x = ( k * b + 1 ) * b * ( b – 1 ) / 2 ，k可以直接枚举。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<cmath> #include<cstring> #define inf 1000000000 #define ll long long #define mod 1000000007 using namespace std; int read() { int x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } ll a,b,ans; int main() { a=read();b=read(); for(ll i=1;i<=a;i++) ans=(ans+(i*b+1)%mod*(b*(b-1)/2%mod))%mod; printf("%I64d",ans); return 0; } |
OI 课件=>
