BZOJ 1101 [POI2007]Zap(莫比乌斯反演)-程序员宅基地

技术标签: php  数据结构与算法  

 

【题目链接】 http://www.lydsy.com/JudgeOnline/problem.php?id=1101

 

【题目大意】

  求[1,n][1,m]内gcd=k的情况

 

【题解】

  考虑求[1,n][1,m]里gcd=k

  等价于[1,n/k][1,m/k]里gcd=1

  考虑求[1,n][1,m]里gcd=1

  结果为sum(miu[d]*(n/d)*(m/d))

  预处理O(n^1.5)

  由于n/d只有sqrt(n)种取值,所以可以预处理出miu[]的前缀和 询问时分段求和

 

【代码】

#include <cstdio>
#include <algorithm>
const int N=50010;
using namespace std;
typedef long long ll;
int T,a,b,c,d,k;
int tot,p[N],miu[N],sum[N],v[N];
void mobius(int n){
    int i,j;
    for(miu[1]=1,i=2;i<=n;i++){
        if(!v[i])p[tot++]=i,miu[i]=-1;
        for(j=0;j<tot&&i*p[j]<=n;j++){
            v[i*p[j]]=1;
            if(i%p[j])miu[i*p[j]]=-miu[i];else break;
        }
    }for(i=1;i<=n;i++)sum[i]=sum[i-1]+miu[i];
}
ll cal(int n,int m){
    ll t=0;
    if(n>m)swap(n,m);
    for(int i=1,j=0;i<=n;i=j+1)
    j=min(n/(n/i),m/(m/i)),t+=(ll)(sum[j]-sum[i-1])*(n/i)*(m/i);
    return t;
}
int main(){
    mobius(50000);
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&a,&b,&k);
        printf("%lld\n",cal(a/k,b/k));
    }return 0;
}

  

转载于:https://www.cnblogs.com/forever97/p/bzoj1101.html

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/weixin_30553777/article/details/96980447

智能推荐

EasyCode生成后需要的改动_easycode 生成的实体字段名可以修改吗-程序员宅基地

文章浏览阅读256次。生成后需要做的改动:1.Application.ymlserver: port: 8080spring: datasource: url: jdbc:mysql://127.0.0.1:3306/database?useUnicode=true&characterEncoding=UTF-8 username: root password: 123456 type: com.alibaba.druid.pool.DruidDataSource d_easycode 生成的实体字段名可以修改吗

计算机五大组成部件和工作过程_计算机工作的五个主要过程-程序员宅基地

文章浏览阅读1.7w次,点赞3次,收藏41次。计算机工作的过程以取数指令为例 启动机器,首先 PC ( 程序计数器 ) 存放的是一条指令的地址,对于这条指令指令送到存储器的 MAR ( 地址寄存器 ) 中。并命令存储器执行读操作,然后将读取的内容送至MDR ( 数据寄存器 ) 。然后MDR 讲指令送到 IR ( 指令寄存器 ) 中。这里就完成了获取指令。( 1-4 )IR存放当前指令,然后指令由 IR 送到 CU 控制单元,C..._计算机工作的五个主要过程

【MyBatis框架】MyBatis的逆向工程生成代码,如何生成逆向工程_mybatis逆向工程生成-程序员宅基地

文章浏览阅读611次。1:逆向工程是什么。 介绍: mybatis的一个主要的特点就是需要程序员自己编写mybatis.xml的sql语句,如果表太多的话,自己写就难免会很麻烦,所以mybatis官方提供了一个逆向工程,可以针对单表自动生成mybatis执行所需要的代码(包括mapper.xml、mapper.java、po..)。一般在开发中,常用的逆向工程方式是通过数据库的表生成代码。2:怎么使用逆向工程_mybatis逆向工程生成

杭电ACM2075A|B?------20140801_杭电acm2075 java-程序员宅基地

文章浏览阅读411次。#includeint main(){ int n; __int64 a,b; scanf("%d",&n); while(n--) { scanf("%I64d%I64d",&a,&b); if(a%b==0) printf("YES\n"); else printf("NO\n");_杭电acm2075 java

三重form提交_html form 服务器收到3次-程序员宅基地

文章浏览阅读480次。网上大多都说form表单不能重叠,经过测试可以通过js来实现form多重提交 Html: " method="post" enctype="multipart/form-data" onsubmit="doSubmit();"> JS代码:function doSubmit(){ testForm.action = "http://.....";_html form 服务器收到3次

NLP(四十四)使用keras-bert加载BERT模型的两种方法_keras bert当作一层输入-程序员宅基地

文章浏览阅读3.8k次,点赞8次,收藏37次。  keras-bert是Keras框架加载BERT模型的Python第三方模块,在之前的文章中,笔者介绍了如何使用keras-bret来实现不同的NLP任务,比如:NLP(三十四)使用keras-bert实现序列标注任务NLP(三十五)使用keras-bert实现文本多分类任务NLP(三十六)使用keras-bert实现文本多标签分类任务NLP(三十七)使用keras-bert实现英语序列标注任务NLP(三十九)使用keras-bert实现完形填空及简单的文本纠错功能NLP(四十二)人物关系_keras bert当作一层输入

随便推点

android实现通话录音获取上传实现过程记录。_android软电话实现通话录音-程序员宅基地

文章浏览阅读7.5k次,点赞3次,收藏24次。项目里提了一个需求,需要通话录音功能(录制双方的声音),并上传到后台。(软件是内部人员工作使用不涉及个人隐私)首先想到的肯定是用APP来进行录音,可控性比较高,测试了android自带的MediaRecorder与AudioRecord结果发现都只能录到呼叫方的声音,查找资料发现录音的来源中有一个MediaRecorder.AudioSource.VOICE_CALL可以录制双方声音,不过5...._android软电话实现通话录音

Unity5.x中Skybox天空盒子的设置的两种方法_unity 编辑器 scene 视口不显示天空盒-程序员宅基地

文章浏览阅读3w次。在Unity5.0以上版本中,天空盒子的设置发生了变化;如果设置不当,在Scene视图中是看不到天空盒子的;第一个方法仅能修改Game视图中的天空盒子(仅渲染当前摄像机),Scene视图是没有的;第二种方法是场景中所有摄像机都会看到的天空盒子,所以在Scene视图中是可以看到的;这点需注意!方法/步骤1导入天空盒子资源包如果已经导入天空盒子资源包_unity 编辑器 scene 视口不显示天空盒

django 序列化组件Serializer_django serializer-程序员宅基地

文章浏览阅读4.8k次,点赞2次,收藏4次。django 序列化组件的一点心得_django serializer

ccpc网络赛1008 Fishing Master_ccpc relay-程序员宅基地

文章浏览阅读214次。题目:题目大意:就是小学学的那种,即烧水,又扫地,还浇花,求所用的时间最短的那种时间合理分配问题。第一行给出所需测试的样例数,第二行给出鱼的条数和抓每条鱼所需时间,第三行给出煮每条鱼所用的时间。抓鱼的同时不能放鱼,但是可以超时煮鱼。求出抓完所有鱼并且煮熟所需的最短时间。思路:给出的标准题解思路是这样婶儿滴:为了锻炼寄几的表达能力呢,我就用自己的语言再复述一遍..._ccpc relay

27-正则表达式一_27%-6的表达式子-程序员宅基地

文章浏览阅读104次。第二十七章.正则表达式一一.正则表达式正则表达式是一个查找和替换字符串的强有力的工具。在 JavaScript 中,正则表达式通过内置的“RegExp”类的对象来实现,并与字符串集成。例子常规写法://提取出str中所有的数字组成一个数组 ["188","38","3","29"]let str = "特务兔187伟哥38小希3薄荷29";function fn( str ){ let arr = []; let s = ""; for (le_27%-6的表达式子

php mysql 注入漏洞_PHP安全:SQL注入漏洞防护-程序员宅基地

文章浏览阅读1.4k次,点赞7次,收藏29次。原标题:PHP安全:SQL注入漏洞防护SQL注入是最危险的漏洞之一,但也是最好防护的漏洞之一。本文介绍在PHP的编码中合理地使用MySQL提供的预编译进行SQL注入防护,在PHP中使用PHP数据对象扩展或MySQLi扩展连接数据库,并且对SQL语句进行预编译处理。如果在一些项目中无法使用预编译来防止SQL注入,可以采用传统方法来验证用户的输入是否合法,严格控制输入参数的数据类型,过滤非法字符,拦截..._php max_prepared_stmt_count