题意:http://hzwer.com/4205.html
同hdu1695
#include <iostream>
#include <cstring>
#include <cmath>
#include <cstdio>
using namespace std;
#define LL long long
#define MMX 50010
int mu[MMX],msum[MMX];
LL n;
bool check[MMX];
int prime[MMX]; void Moblus() //莫比乌斯反演,mu[i]为莫比乌斯函数
{
memset(check,false,sizeof(check));
mu[] = ;
int tot = ;
for(int i = ; i <= MMX; i++)
{
if( !check[i] )
{
prime[tot++] = i;
mu[i] = -;
}
for(int j = ; j < tot; j++)
{
if(i * prime[j] > MMX) break;
check[i * prime[j]] = true;
if( i % prime[j] == )
{
mu[i * prime[j]] = ;
break;
}
else
{
mu[i * prime[j]] = -mu[i];
}
}
}
msum[]=mu[]; //求和,求G的时候用
for (int i=;i<=MMX;i++)
msum[i]=msum[i-]+mu[i];
} LL G(int n,int m) //G(x,y)表示有多少组x<=n,y<=m,且x,y互质 ((x,y)和(y,x)算两组)
{
LL ans = ;
if(n > m) swap(n,m);
for(int i = , la = ; i <= n; i = la+)
{
la = min(n/(n/i),m/(m/i));
ans += (LL)(msum[la] - msum[i-])*(n/i)*(m/i); //事先预处理:msum[n]=SUM(mu[1..n])
}
return ans;
} int main()
{
int T;
cin>>T;
Moblus();
for (int zy=; zy<=T; zy++)
{
int a,b,c,d,k;
//cin>>b>>d>>k;
scanf("%d%d%d\n",&b,&d,&k);
if (b>d) swap(b,d); //assume b<d
b=b/k;
d=d/k; LL ans1 = G(b,d); printf("%lld\n",ans1);
}
}
1020 | root | 1003 | Accepted | 564K | 3819MS | G++ | 1.62K | 2014-11-16 18:08:01 |
POI2007_zap 莫比乌斯反演的更多相关文章
-
hdu1695 GCD(莫比乌斯反演)
题意:求(1,b)区间和(1,d)区间里面gcd(x, y) = k的数的对数(1<=x<=b , 1<= y <= d). 知识点: 莫比乌斯反演/*12*/ 线性筛求莫比乌 ...
-
BZOJ 2154: Crash的数字表格 [莫比乌斯反演]
2154: Crash的数字表格 Time Limit: 20 Sec Memory Limit: 259 MBSubmit: 2924 Solved: 1091[Submit][Status][ ...
-
BZOJ2301: [HAOI2011]Problem b[莫比乌斯反演 容斥原理]【学习笔记】
2301: [HAOI2011]Problem b Time Limit: 50 Sec Memory Limit: 256 MBSubmit: 4032 Solved: 1817[Submit] ...
-
Bzoj2154 Crash的数字表格 乘法逆元+莫比乌斯反演(TLE)
题意:求sigma{lcm(i,j)},1<=i<=n,1<=j<=m 不妨令n<=m 首先把lcm(i,j)转成i*j/gcd(i,j) 正解不会...总之最后化出来的 ...
-
莫比乌斯函数筛法 &; 莫比乌斯反演
模板: int p[MAXN],pcnt=0,mu[MAXN]; bool notp[MAXN]; void shai(int n){ mu[1]=1; for(int i=2;i<=n;++i ...
-
【BZOJ-2440】完全平方数 容斥原理 + 线性筛莫比乌斯反演函数 + 二分判定
2440: [中山市选2011]完全平方数 Time Limit: 10 Sec Memory Limit: 128 MBSubmit: 2371 Solved: 1143[Submit][Sta ...
-
hdu.5212.Code(莫比乌斯反演 &;&; 埃氏筛)
Code Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submi ...
-
CSU 1325 莫比乌斯反演
题目大意: 一.有多少个有序数对(x,y)满足1<=x<=A,1<=y<=B,并且gcd(x,y)为p的一个约数: 二.有多少个有序数对(x,y)满足1<=x<=A ...
-
HDU1695 GCD(莫比乌斯反演)
传送门 看了1个多小时,终于懂了一点了 题目大意:给n,m,k.求gcd(x,y) = k(1<=x<=n, 1<=y<=m)的个数 思路:令F(i)表示i|gcd(x,y)的 ...
随机推荐
-
iOS 消息推送(APNs) 傻瓜式教程
也可以去我的简书页面查看这篇文章 首先: 1.做iOS消息推送需要真机测试 2.做iOS消息推送需要有付费的开发者账号 是否继续看帖? 先学习一下相关的知识吧! 因为中途可能会遇到一些问题,这篇文章或 ...
-
HDOJ/HDU 2537 8球胜负(水题.简单的判断)
Problem Description 8球是一种台球竞赛的规则.台面上有7个红球.7个黄球以及一个黑球,当然还有一个白球.对于本题,我们使用如下的简化规则:红.黄两名选手轮流用白球击打各自颜色的球, ...
-
使用Gird++打印出现“Retrieving the COM class factory for component with CLSID”的解决办法
我们的接口需要返回一个gird++生成PDF文件的二进制数据,在本地测试都很好,发布到服务器上一直出现“Retrieving the COM class factory for component w ...
-
CentOS 7 启动VNC失败问题
开机后发现VNC服务没有启启来,提示我们使用journalctl -xn查看错误信息,提示信息如下: Sep :: localhost.localdomain systemd[]: Unit vncs ...
-
团队合作-如何避免JS冲突
解决JS冲突的演化过程 1.用匿名函数将脚本包裹起来,可以有效控制全局变量,避免冲突隐患 (function(){})(): 2.定义一个全局作用域的变量str,可以帮助我们在不同匿名函数间通信 严格 ...
-
正交矩阵、EVD、SVD
原文地址:https://www.jianshu.com/p/1004dd342fe2 一.正交矩阵 二.EVD 特征值分解(Eigen Value Decomposition, EVD). 对于对称 ...
-
策略模式(Strategy Model)
定义:一个类的行为或算法能在运行时被改变,将一组算法封装成一系列对象,通过这些对象灵活改变系统功能: 实现方式: 首先定义个strategy接口,然后创建一系列对象(strategy objects) ...
-
线程池threadPools
1.线程池是用来存储线程的容器 2.Executors.newFixedThreadPool(int n);创建线程池,并且设置线程池的容量为n 3.submit开启线程 4.会返回一个对象futur ...
-
上传文件服务器与web内容服务分离
现在难点在: 1\单击表单提交按钮后,图片上传到图片服务器,文字内容上传web服务器数据库,这两个服务器分别在两个城市. 2\图片不能通过web服务器中转. 3\web服务器内 ...
-
linux JAVA_HOME和 java -version不匹配
~/.bashrc 中更新了jdk, JAVA_HOME 起效果了,但是java -version还是老的. 原因是/usr/bin/java 和usr/bin/javac是一个链接,得改. 使用 ...