题目链接:
http://acm.hdu.edu.cn/showproblem.php?pid=4135
题目大意:
求区间[a, b]中与N互质的数目。
解题思路:
首先对n求出所有素因子。
对于区间[1, m]中,只需要对n素因子求出所有子集,就可以求出所有的与n不互质的数目num,那么互质的数就是m-num;
对于区间[a, b],就等于[1, b]的数目 - [1,a - 1]的数目。
#include<iostream>
using namespace std;
typedef long long ll;
const int maxn = 1e6 + ;
ll a[], tot;
ll gcd(ll a, ll b)
{
return b == ? a : gcd(b, a % b);
}
void init(ll n)//求出n的素因子
{
tot = ;
for(ll i = ; i * i <= n; i++)
{
if(n % i == )
{
a[tot++] = i;
while(n % i == )n /= i;
}
}
if(n != )a[tot++] = n;
}
ll sum(ll m)//求[1, m]中与n互质的个数
{
ll ans = ;
for(int i = ; i < ( << tot); i++)//a数组的子集
{
ll num = ;
for(int j = i; j; j >>= )if(j & )num++;//统计i的二进制中1的个数
ll lcm = ;
for(int j = ; j < tot; j++)
if(( << j) & i)
{
lcm = lcm / gcd(lcm, a[j]) * a[j];
if(lcm > m)break;
}
if(num & )ans += m / lcm;//奇数加上
else ans -= m / lcm;//偶数减去
}
return m - ans;
}
ll n, l, r;
int main()
{
int T, cases = ;
cin >> T;
while(T--)
{
cin >> l >> r >> n;
init(n);
cout<<"Case #"<<++cases<<": "<<sum(r) - sum(l - )<<endl;
}
return ;
}
hdu-4135 Co-prime---容斥定理经典&&求1-m中与n互质的数目的更多相关文章
-
题解报告:hdu 4135 Co-prime(容斥定理入门)
Problem Description Given a number N, you are asked to count the number of integers between A and B ...
-
HDU 4135 Co-prime(容斥+数论)
Co-prime Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Su ...
-
HDU 1695 GCD(容斥定理)
GCD Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submis ...
-
HDU 4135 Co-prime(容斥:二进制解法)题解
题意:给出[a,b]区间内与n互质的个数 思路:如果n比较小,我们可以用欧拉函数解决,但是n有1e9.要求区间内互质,我们可以先求前缀内互质个数,即[1,b]内与n互质,求互质,可以转化为求不互质,也 ...
-
HDU5768Lucky7(中国剩余定理+容斥定理)(区间个数统计)
When ?? was born, seven crows flew in and stopped beside him. In its childhood, ?? had been unfortun ...
-
HDU 4135 Co-prime 欧拉+容斥定理
Co-prime Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Su ...
-
HDU - 4135 Co-prime 容斥定理
题意:给定区间和n,求区间中与n互素的数的个数, . 思路:利用容斥定理求得先求得区间与n互素的数的个数,设表示区间中与n互素的数的个数, 那么区间中与n互素的数的个数等于.详细分析见求指定区间内与n ...
-
HDU 1695 GCD 欧拉函数+容斥定理 || 莫比乌斯反演
GCD Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)Total Submiss ...
-
HDU 2841 Visible Trees(容斥定理)
Visible Trees Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) To ...
随机推荐
-
JavaWeb的国际化
国际化 1.国际化开发概述 1.1.软件的国际化 软件开发时,要使它能同时应对世界不同地区和国家的方法,并针对不同地区和国家的方法,提供相应的,符合来访者阅读习惯的页面或数据 国际化简称:i18n : ...
-
如何在ASP.NET 5中使用ADO.NET
(此文章同时发表在本人微信公众号"dotNET每日精华文章",欢迎右边二维码来关注.) 题记:ASP.NET 5是一个全新的平台,在这个平台上也带来一些全新的函数库.不过这并非意味 ...
-
【SSH三大框架】Hibernate基础第二篇:编写HibernateUtil工具类优化性能
相对于上一篇中的代码编写HibernateUtil类以提高程序的执行速度 首先,仍然要写一个javabean(User.java): package cn.itcast.hibernate.domai ...
-
Cocos2d-x 游戏存档
游戏存档功能能够保存游戏中数据.让玩家游戏能够延续. 单机游戏更为重要.而CCUserDefault能够作轻量级数据库使用,用来存储数据,支持数据类型bool,int, float, double, ...
-
android-misc-widgets四向(上下左右)抽屉bug修复版--转载
android-misc-widgets四向(上下左右)抽屉bug修复版 2013-08-04 08:58:13 标签:bug down top panel slidingdrawer 原创作品,允 ...
-
c++ dynamic_cast 和 static_cast 的区别
今天在看王道宝典的时候看到dynamic_cast ,一直都没用过,也不了解,今天来总结一下. dynamic_cast 和 static_cast 都可以用来强制转换指针类型,但不同的是dynami ...
-
46. Permutations C++回溯法
基本的回溯法 注意每次回溯回来要把上次push_back()进去的数字pop掉! class Solution { public: void backTrack(vector<int> n ...
-
读配置文件property文件
import java.io.IOException;import java.util.Properties; import org.springframework.core.io.support.P ...
-
CreateDialog()与CreateDialogIndrect()
CreateDialog() 概述 函数功能:CreateDialog宏从一个对话框模板资源创建一个无模式的对话框,CreateDiaog宏使用CreateDialogParam函数. 函数原型:HW ...
-
【leetcode 简单】 第八十七题 两整数之和
不使用运算符 + 和-,计算两整数a .b之和. 示例: 若 a = 1 ,b = 2,返回 3. class Solution: def getSum(self, a, b): "&quo ...