收获:
1、积性函数的积也是积性函数,基本的积性函数:常数函数,正比例函数,欧拉函数,Mobius函数,积性函数一般都知道表达式,所以一般都可以在线性筛时搞定。
2、遇到整除求和时,这个东西就已经是最简了,所以可以考虑提出它,然后尝试搞后边的东西的前缀和,如果可以成功,那么就可以在O(sqrt(n))的复杂度做了。
/**************************************************************
Problem: 2693
User: idy002
Language: C++
Result: Accepted
Time:4692 ms
Memory:118504 kb
****************************************************************/ #include <cstdio>
#include <iostream>
#define M 100000009
using namespace std; typedef long long dnt; int prm[], isnot[], mu[], dm[], ptot; void init( int n ) {
mu[] = ;
dm[] = ;
for( int i=; i<=n; i++ ) {
if( !isnot[i] ) {
prm[++ptot] = i;
mu[i] = -;
dm[i] = (dnt)i*(-i) % M;
}
for( int j=; j<=ptot && i*prm[j]<=n; j++ ) {
int k = i*prm[j];
isnot[k] = true;
if( i%prm[j]== ) {
mu[k] = ;
dm[k] = (dnt)k/i*dm[i] % M;
break;
}
mu[k] = -mu[i];
dm[k] = (dnt)dm[i]*dm[prm[j]] % M;
}
}
for( int i=; i<=n; i++ ) {
dm[i] += dm[i-];
if( dm[i]>=M ) dm[i]-=M;
if( dm[i]< ) dm[i]+=M;
}
}
inline dnt S( dnt n, dnt m ) {
return ((+n)*n/%M) * ((+m)*m/%M) % M;
}
dnt calc( int n, int m ) {
if( n>m ) swap(n,m);
dnt rt = ;
for( dnt d=; d<=n; d++ ) {
dnt dd = min( n/(n/d), m/(m/d) );
rt += S(n/d,m/d) * (dm[dd]-dm[d-]) % M;
if( rt>=M ) rt-=M;
if( rt< ) rt+=M;
d = dd;
}
return rt;
}
int main() {
init();
int T;
scanf( "%d", &T );
while( T-- ) {
int n, m;
scanf( "%d%d", &n, &m );
printf( "%lld\n", calc(n,m) );
}
}