jzptab

【问题描述】

求：

 

多组询问

【输入格式】

一个正整数T表示数据组数

接下来T行 每行两个正整数 表示N、M

【输出格式】

T行 每行一个整数 表示第i组数据的结果

【样例输入】

1

4 5

【样例输出】

122

【数据范围】

T <= 10000

N, M<=10000000

---

题解：

即后面那个部分为 H[T]，H[T]是积性函数，求详细证明的话将T和d展开为质因数次幂相乘的形式，考虑线性筛中枚举的质数与被筛数的性质即可

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 #include
          
            7 using namespace std; 8 typedef long long ll; 9 const int maxn = 1e7 + 1;10 const int mod = 1e8 + 9;11 int cnt;12 int h[maxn];13 int pri[maxn];14 int sum[maxn];15 bool vis[maxn];16 inline void Scan(int &x)17 {18 char c;19 bool o = false;20 while(!isdigit(c = getchar())) o = (c != '-') ? o : true;21 x = c - '0';22 while(isdigit(c = getchar())) x = x * 10 + c - '0';23 if(o) x = -x;24 }25 inline void Sieve()26 {27 h[1] = 1;28 for(int i = 2; i <= maxn; ++i)29 {30 if(!vis[i]) pri[++cnt] = i, h[i] = ((-(long long) i * i % mod) + mod + i) % mod;31 for(int j = 1; j <= cnt; ++j)32 {33 int s = pri[j];34 long long k = (long long) i * s;35 if(k > maxn) break;36 vis[k] = true;37 if(!(i % s))38 {39 h[k] = (long long) s * h[i] % mod;40 break;41 }42 else h[k] = (long long) h[s] * h[i] % mod;43 }44 }45 for(int i = 1; i <= maxn; ++i) sum[i] = (sum[i - 1] + h[i]) % mod;46 }47 inline int Sum(int n, int m)48 {49 return ((long long) n * (n + 1) >> 1) % mod * (((long long) m * (m + 1) >> 1) % mod) % mod;50 }51 inline int Mobius(int n, int m)52 {53 int res = 0, last = 0;54 if(n > m) swap(n, m);55 for(int i = 1; i <= n; i = last + 1)56 {57 last = min(n / (n / i), m / (m / i));58 res = (res + (long long) Sum(n / i, m / i) * ((sum[last] - sum[i - 1] + mod) % mod) % mod) % mod;59 }60 return res;61 }62 int main()63 {64 Sieve();65 int n;66 Scan(n);67 int a, b;68 while(n--)69 {70 Scan(a), Scan(b);71 printf("%d\n", Mobius(a, b));72 }73 }