[HOJ 220] E. code

作法：

如果題目沒有$i\neq j$的條件的話，式子就可以寫成$\displaystyle (\sum_{i=1}^{n} n\% i)(\sum_{i=1}^{m} m\% i)$，因此這部份可以先分開算再乘起來。至於要怎麼計算$\displaystyle \sum_{i=1}^{n} n\% i$，一樣是把商一樣的區間合併起來看，因為$n$除以從$i$一直到$n/(n/i)$（這裡是整數除法）的這些數都會得到一樣的商，所以在這個區間裡$n\% i$會是一個等差數列，可以合併起來一起算。最後則是要扣掉$i=j$的部份，也就是要計算$\displaystyle \sum_{i=1}^{min(n,m)} (n\% i)(m\% i)$，這一樣可以用剛才的技巧，只不過區間的右端點必須取成$min(m/(m/i),n/(n/i))$而已。這部份則會變成一個二次函數在一個區間裡的所有函數值的總和，而這東西不難用$\displaystyle \sum k^2$的公式求得。

code :

#include<bits/stdc++.h>
#define LL long long
#define MOD 1000000007
using namespace std;
 
LL cal(LL n)
{
    LL ret=0 ;
    for(LL i=1;i<=n;)
    {
        LL j=n/(n/i) , q=n/i ;
        ret+=n*(j-i+1)-q*((i+j)*(j-i+1)/2%MOD)%MOD ;
        ret%=MOD ;
        i=j+1 ;
    }
    return ret ;
}
 
inline LL get2(LL x)
{
    return x*(x+1)%MOD*(2*x+1)%MOD*166666668%MOD ;
}
 
main()
{
    int T ; scanf("%d",&T) ;
    while(T--)
    {
        LL n,m ; scanf("%lld%lld",&n,&m) ;
        LL ans=cal(n)*cal(m)%MOD , sub=0 ;
        for(LL i=1;i<=min(n,m);)
        {
            LL j=min(n/(n/i),m/(m/i)) ;
            LL q1=n/i , q2=m/i ;
            sub+=q1*q2%MOD*(get2(j)-get2(i-1))%MOD ;
            sub%=MOD ;
            sub-=(q1*m%MOD+q2*n%MOD)*((i+j)*(j-i+1)/2%MOD)%MOD ;
            sub%=MOD ;
            sub+=n*m%MOD*(j-i+1)%MOD ;
            sub%=MOD ;
            i=j+1 ;
        }
        printf("%lld\n",((ans-sub)%MOD+MOD)%MOD) ;
    }
}