2693: jzptab - BZOJ

Description

Input

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

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

1

4 5

Sample Output

122

HINT

T <= 10000

N, M<=10000000

题解君:http://hi.baidu.com/mikeni2006/item/b4f78a4520de9bab61d7b985

看了一上午才看懂,最后终于在lazycal的帮助下想出来了

我们需要先预处理出那个奇怪的前缀和就是

d              
                     
                     
                     
                     
                     
                     
                     
                     
        Σ    d*  Σ    d‘*μ(d‘)
                     
                     
                     
                     
                     
                     
                     
                 i=1    
 d‘|d

然后因为trunc(n/i)和trunc(m/i)都只有根号级别个值,也就是只要枚举这些值就行了

为了跑得快,类型用的longint,然后写了很多int64函数

 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
60 read(n,m);
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;
91 read(t);
92 while t>0 do
93 begin
94 dec(t);
95 main;
96 end;
97 end.

View
Code

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

时间: 06-05

2693: jzptab - BZOJ的相关文章

【莫比乌斯反演】关于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( 莫比乌斯反演 )

速度居然#2...目测是因为我没用long long.. 求∑ lcm(i, j) (1 <= i <= n, 1 <= j <= m) 化简之后就只须求f(x) = x∑u(d)*d (d | x) 然后就是分块了... ------------------------------------------------------------------- #include<bits/stdc++.h> using namespace std; typedef long

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

[省选]省选知识点进度

联赛之后记录一下自己的知识点学习情况(按开始时间先后顺序) 可持久化数据结构 [BZOJ 3123]森林 树上主席树 启发式合并 LCA [BZOJ 4826]影魔 区间修改主席树 标记永久化 [BZOJ 2735]世博会 主席树 切比雪夫距离转曼哈顿距离 [BZOJ 3166]Alo 可持久化01Trie [BZOJ 3689]异或之 可持久化01Trie [BZOJ 3261]最大异或和 可持久化01Trie 树套树 [COGS 257]动态排名系统 树状数组套主席树 [BZOJ 2141]