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 Data Constraint Hint 【样例解释】 答案为(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 【数据范围】 对于10%的数据n,m<=1000； 　　对于30%的数据 n,m<=1000000； 　　另有30%的数据n<=100，m<=10^9； 　　对于100%的数据n,m<=10^9。 Σni=1Σmj=1( n mod i ) ( m mod j ) // i!=j
=Σni=1Σmj=1( n-i⌊n/i⌋ ) ( m-j⌊m/j⌋ ) // i!=j
=Σni=1Σmj=1( n-i⌊n/i⌋ ) ( m-j⌊m/j⌋ ) - Σmin(n,m)i=1( n-i⌊n/i⌋ ) ( m-i⌊m/i⌋ )
=Σni=1( n-i⌊n/i⌋ )Σmj=1( m-j⌊m/j⌋ ) - Σmin(n,m)i=1( nm+i2⌊n/i⌋⌊m/j⌋ -⌊m/i⌋ n*i - i * m⌊n/i⌋ )
运用分块，固定⌊n/i⌋与⌊m/j⌋
对于i2可以用连续自然数平方和公式求出。 #include #include #include using namespace std ; typedef long long ll ; ll i , j , k , n , m , mo = 19940417 , ine = 3323403 ; ll sigma( ll a , ll b ) { return ( a + b ) * ( b - a + 1 ) / 2 % mo ; } ll Squ_sigma( ll a , ll b ) { ll A = ( a - 1 ) * a % mo * ( 2 * a - 1 ) % mo * ine % mo ; ll B = ( b + 1 ) * b % mo * ( 2 * b + 1 ) % mo * ine % mo ; return ( B - A ) % mo ; } ll calc( ll n ) { ll A = n * n % mo ; ll B = 0 ; for( ll a = 1 , b = 0 ; a<=n ; a=b+1 ) { b = n / ( n / a ) ; B = ( B + sigma( a , b ) * ( n / a ) % mo ) % mo ; } return ( A - B ) % mo ; } int main() { scanf("%lld%lld",&n,&m ) ; ll A = calc( n ) , B = calc( m ) ; ll ans = ( A * B ) % mo ; ll sm = min( n , m ) ; ans = ( ans - sm * n % mo * m % mo ) % mo ; for( i = 1 ; i <= sm ; i = j + 1 ) { ll nn = n / ( n / i ) ; ll mm = m / ( m / i ) ; j = min( nn , mm ) ; j = min( j , sm ) ; ll va1 = ( n / i ) % mo , va2 = ( m / i ) % mo ; ans = ( ans - va1 * va2 % mo * Squ_sigma( i , j ) % mo ) % mo ; va1 = n / i * m % mo * sigma( i , j ) % mo ; va2 = m / i * n % mo * sigma( i , j ) % mo ; ans = ( ans + va1 + va2 ) % mo ; } printf("%lld", ( ans+mo ) % mo ) ; } 看到模要想到 a % b == a-a/b*a，想办法固定sigma内的内容