# 2693: jzptab - BZOJ

Description

Input

Output

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

1

4 5

Sample Output

122

HINT

T <= 10000

N, M<=10000000

d

Σ    d*  Σ    d‘*μ(d‘)

i=1
d‘|d

 1 const
2     maxn=10000010;
3     h=100000009;
4 var
5     flag:array[0..maxn]of boolean;
6     f,s:array[0..maxn]of longint;
7     p:array[0..1000000]of longint;
8     t,n,m,tot:longint;
9
10 function max(x,y:longint):longint;
11 begin
12     if x>y then exit(x);
13     exit(y);
14 end;
15
16 function min(x,y:longint):longint;
17 begin
18     if x<y then exit(x);
19     exit(y);
20 end;
21
22 function get(a:longint):longint;
23 begin
24     exit(((int64(a)*a+a)>>1)mod h);
25 end;
26
27 procedure pre;
28 var
29     i,j:longint;
30 begin
31     f[1]:=1;
32     for i:=2 to 10000000 do
33       begin
34         if flag[i]=false then
35           begin
36             inc(tot);
37             p[tot]:=i;
38             f[i]:=1-i+h;
39           end;
40         for j:=1 to tot do
41           begin
42             if int64(p[j])*i>10000000 then break;
43             flag[p[j]*i]:=true;
44             if i mod p[j]=0 then
45               begin
46                 f[p[j]*i]:=f[i];
47                 break;
48               end
49             else f[p[j]*i]:=int64(f[i])*f[p[j]]mod h;
50           end;
51       end;
52     for i:=1 to 10000000 do
53       s[i]:=(int64(s[i-1])+int64(f[i])*i)mod h;
54 end;
55
56 procedure main;
57 var
58     i,j,t,li,ri,lj,rj,l,r,ans:longint;
59 begin
61     if n>m then
62     begin
63       t:=n;n:=m;m:=t;
64     end;
65     ans:=0;
66     i:=1;
67     while sqr(i)<=n do
68       begin
69         ans:=(int64(ans)+((int64(f[i])*i mod h)*get(trunc(n/i))mod h)*get(trunc(m/i)))mod h;
70         inc(i);
71       end;
72     j:=trunc(m/i);
73     i:=trunc(n/i);
74     while (i>0) and (j>0) do
75       begin
76         ri:=trunc(n/i);
77         li:=trunc(n/(i+1))+1;
78         lj:=trunc(m/(j+1))+1;
79         rj:=trunc(m/j);
80         l:=max(li,lj);
81         r:=min(ri,rj);
82         if l<=r then ans:=(int64(ans)+(int64(s[r]-s[l-1]+h)*get(i)mod h)*get(j))mod h;
83         if ri<=rj then dec(i)
84         else dec(j);
85       end;
86     writeln(ans);
87 end;
88
89 begin
90     pre;
92     while t>0 do
93       begin
94         dec(t);
95         main;
96       end;
97 end.

View
Code

2693: jzptab - BZOJ,布布扣,bubuko.com

## 【莫比乌斯反演】关于Mobius反演与lcm的一些关系与问题简化(BZOJ 2154 crash的数字表格&amp;&amp;BZOJ 2693 jzptab)

BZOJ 2154 crash的数字表格 Description 今天的数学课上,Crash小朋友学习了最小公倍数(Least Common Multiple).对于两个正整数a和b,LCM(a, b)表示能同时被a和b整除的最小正整数.例如,LCM(6, 8) = 24.回到家后,Crash还在想着课上学的东西,为了研究最小公倍数,他画了一张N*M的表格.每个格子里写了一个数字,其中第i行第j列的那个格子里写着数为LCM(i, j).一个4*5的表格如下: 1 2 3 4 5 2 2 6 4

## bzoj 2693: jzptab 线性筛积性函数

2693: jzptab Time Limit: 10 Sec  Memory Limit: 512 MBSubmit: 444  Solved: 174[Submit][Status][Discuss] Description Input 一个正整数T表示数据组数 接下来T行 每行两个正整数 表示N.M Output T行 每行一个整数 表示第i组数据的结果 Sample Input 1 4 5 Sample Output 122 HINT T <= 10000 N, M<=10000000

## BZOJ 2693: jzptab [莫比乌斯反演 线性筛]

2693: jzptab Time Limit: 10 Sec  Memory Limit: 512 MBSubmit: 1194  Solved: 455[Submit][Status][Discuss] Description Input 一个正整数T表示数据组数 接下来T行 每行两个正整数 表示N.M Output T行 每行一个整数 表示第i组数据的结果 Sample Input 1 4 5 Sample Output 122 HINT T <= 10000 N, M<=1000000

## BZOJ 2693 jzptab 【莫比乌斯反演】

Description Hint T <= 10000 N, M<=10000000 Solution 和 BZOJ 2154 数字表格 几乎一样,只不过询问变成多组,之前的复杂度又过不了了 依旧写开答案 又有两个枚举量 我们尝试改变求和指标+前缀和继续减掉一个枚举量 于是就有了 对于这个东西我们定义它为 h ( D ) 使可以进行前缀和预处理的 考虑枚举 i 和 i 的倍数 然而这样的处理显然也是接受不了的 似乎只有O(n)的复杂度才可能接受 能不能把 h 放到线性筛之中处理出来呢 对于一个

## BZOJ 2693 jzptab

http://www.lydsy.com/JudgeOnline/problem.php?id=2693 题解: 考虑把lcm转化成gcd那答案就是然后神奇的设:就有:一样可以枚举 的取值,这是O(√n)的: 然后求f(x,y): 大概证明了一下= = 线性筛之后也可以O(√n)求出f(x,y)总复杂度O(n),常数略大.. 这题显然是卡O(n)过不了呗那就还得优化 预处理这玩意 然后O(√n)就搞出来啦! 设“积性函数的约数和也是积性函数”  ->好像比较显然?所以g(D)是积性函数线性筛裸上

## 【BZOJ】2693: jzptab

http://www.lydsy.com/JudgeOnline/problem.php?id=2693 题意:求\sum_{i=1}^{n} \sum_{j=1}^{m} lcm(i, j), n,m<=1e7, 多个询问q<=10000 #include <bits/stdc++.h> using namespace std; typedef long long ll; const int N=1e7+10, MD=100000009; int p[N], pcnt, mx

## Crash的数字表格 BZOJ 2154 / jzptab BZOJ 2693

jzptab [问题描述] 求: 多组询问 [输入格式] 一个正整数T表示数据组数 接下来T行 每行两个正整数 表示N.M [输出格式] T行 每行一个整数 表示第i组数据的结果 [样例输入] 1 4 5 [样例输出] 122 [数据范围] T <= 10000 N, M<=10000000 题解: 即后面那个部分为 H[T],H[T]是积性函数,求详细证明的话将T和d展开为质因数次幂相乘的形式,考虑线性筛中枚举的质数与被筛数的性质即可 1 #include<cmath> 2 #i