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

2693: jzptab

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 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<=10000000


和上题一样,不过多组数据

利用了和bzoj2820类似的技巧D=di 改变求和指标,这样就可以把Sum提前,剩下的部分处理前缀和

如何处理前缀和:

积性函数的约数和也是积性函数,可以用线性筛

g[i]=约数和D*i*mu[i]

显然g[p]=p*(1-p)

g[i*p[j]] 当p[j]|i时  mu[ii]中ii带有p[j]的话就是0了不能计入,所以p[j]只能在剩下的一块里,也就是只有D变了,所以总的就是p[j]*g[i]

尝试了一下枚举倍数的方法,T了

总结:其实这两道题和gcd=k的个数两道题很像,都是第一题只要求一个,第二题要求多个,然后就要改写式子然后处理前缀和......

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int N=1e7+5,MOD=100000009;
inline int read() {
    char c=getchar();
    int x=0,f=1;
    while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();}
    return x*f;
}
int n,m;
bool notp[N];int p[N];
ll s[N],mu[N],g[N];
void sieve(){
    mu[1]=1;
    g[1]=1;
    for(int i=2;i<N;i++){
        if(!notp[i]) p[++p[0]]=i,mu[i]=-1,g[i]=i-(ll)i*i;
        for(int j=1;j<=p[0]&&i*p[j]<N;j++){
            int t=i*p[j];
            notp[t]=1;
            if(i%p[j]==0){
                mu[t]=0;
                g[t]=(g[i]*p[j])%MOD;
                break;
            }
            mu[t]=-mu[i];
            g[t]=(g[i]*g[p[j]])%MOD;
        }
    }

    for(int i=1;i<N;i++) g[i]=(g[i]+g[i-1])%MOD;    

}
inline ll S(ll x,ll y){
    return ((x*(x+1)/2)%MOD)*((y*(y+1)/2)%MOD)%MOD;
}
int main(){
    sieve();
    int T=read();
    while(T--){
        n=read();
        m=read();
        if(n>m) swap(n,m);
        ll ans=0,r=0;
        for(ll D=1;D<=n;D=r+1){
            r=min(n/(n/D),m/(m/D));
            ans=(ans+S(n/D,m/D)*(g[r]-g[D-1]))%MOD;
        }
        printf("%lld\n",(ans+MOD)%MOD);
    }
}
时间: 12-23

BZOJ 2693: jzptab [莫比乌斯反演 线性筛]的相关文章

bzoj 3309 DZY Loves Math - 莫比乌斯反演 - 线性筛

对于正整数n,定义f(n)为n所含质因子的最大幂指数.例如f(1960)=f(2^3 * 5^1 * 7^2)=3, f(10007)=1, f(1)=0. 给定正整数a,b,求sigma(sigma(f(gcd(i,j)))) (i=1..a, j=1..b). Input 第一行一个数T,表示询问数. 接下来T行,每行两个数a,b,表示一个询问. Output 对于每一个询问,输出一行一个非负整数作为回答. Sample Input 4 7558588 9653114 6514903 445

hdu.5212.Code(莫比乌斯反演 &amp;&amp; 线性筛)

Code Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 300    Accepted Submission(s): 124 Problem Description WLD likes playing with codes.One day he is writing a function.Howerver,his computer b

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

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

bzoj 2440 简单莫比乌斯反演

题目大意: 找第k个非平方数,平方数定义为一个数存在一个因子可以用某个数的平方来表示 这里首先需要考虑到二分才可以接下来做 二分去查找[1 , x]区间内非平方数的个数,后面就是简单的莫比乌斯反演了 容斥原理的思想,首先考虑所有数都属于非平方数 那么就是x 然后对于每一个平方数都要减去,但是这里应该只考虑质数的平方数就可以了 那么就扩展为x - x/(2^2) - x/(3^2) - x/(k^2).... 然后因为中间存在重复减的那么要加回来 -> x - x/(2^2) - x/(3^3) 

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)是积性函数线性筛裸上

BZOJ2693 jzptab 莫比乌斯反演

题意:给定N,M,求$\sum\limits_{i = 1}^N {\sum\limits_{j = 1}^M {lcm(i,j)} }$,多组询问 题解: 设$F(x,y) = \sum\limits_{i = 1}^x {\sum\limits_{j = 1,\gcd (i,j) = 1}^y {ij} }$  $S(x,y) = \frac{{x(x + 1)}}{2}\frac{{y(y + 1)}}{2}$ 我们枚举最大公因数d,则有\[\sum\limits_{i = 1}^N {\

BZOJ 2818 Gcd (莫比乌斯反演 或 欧拉函数)

2818: Gcd Time Limit: 10 Sec  Memory Limit: 256 MB Submit: 2534  Solved: 1129 [Submit][Status][Discuss] Description 给定整数N,求1<=x,y<=N且Gcd(x,y)为素数的 数对(x,y)有多少对. Input 一个整数N Output 如题 Sample Input 4 Sample Output 4 HINT hint 对于样例(2,2),(2,4),(3,3),(4,2)

bzoj 3529 数表 莫比乌斯反演+树状数组

题目大意: 有一张N×m的数表,其第i行第j列(1 < =i < =礼,1 < =j < =m)的数值为能同时整除i和j的所有自然数之和.给定a,计算数表中不大于a的数之和. http://wenku.baidu.com/link?url=1zHluup-GXHdByoQXhMRwRu22Uu15y4DztIr1_hKVxjHJmuLQF4_01UQhLEOR7RJIpsGyfD_5fXrx9DE7sY6JeukaNUY83In097GjUOmZ7K ppt课件中讲的很仔细了 1