转载请注明出处,谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents
by---cxlove
题目:http://acm.hdu.edu.cn/showproblem.php?pid=1695
从1-b和1-d中各取一个数,使得其最大公约数为k。问有多少对。
因为是最大公约数k,所以不仅仅是拥有因子k。除了因子k之外是互质的。
转化成从1---b/k和1---d/k中取出互质的数对。
从一个区间里取出一个数,比他小的互质的部分可以通过欧拉函数搞定,另外一部分通过容斥原理实现。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<cmath>
#define LL long long
#define MOD 1000000007
#define eps 1e-6
#define N 100010
#define zero(a) fabs(a)<eps
using namespace std;
LL eular[N];
int prime[N][15],cnt[N];
void Prime(){
for(int i=2;i<N;i++){
if(eular[i]==i){
eular[i]=i-1;
for(int j=2;j*i<N;j++){
eular[i*j]=eular[i*j]*(i-1)/i;
prime[j*i][cnt[j*i]++]=i;
}
}
eular[i]+=eular[i-1];
}
}
void Init(){
for(int i=1;i<N;i++)
eular[i]=i;
memset(cnt,0,sizeof(cnt));
Prime();
}
LL dfs(int idx,int cur,int now){
LL ret=0;
for(int i=idx;i<cnt[now];i++)
ret+=cur/prime[now][i]-dfs(i+1,cur/prime[now][i],now);
return ret;
}
int main(){
int t,cas=0;
Init();
scanf("%d",&t);
while(t--){
int a,b,c,d,k,l,r;
scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);
if(k==0){
printf("Case %d: 0\n",++cas);
continue;
}
l=b/k;
r=d/k;
if(l>r)
swap(l,r);
//1-l通过欧拉函数求出
LL ans=eular[l];
//1-l中与i互质的数
for(int i=l+1;i<=r;i++)
ans+=l-dfs(0,l,i);
printf("Case %d: %I64d\n",++cas,ans);
}
return 0;
}
分享到:
相关推荐
hdu 1695 GCD(欧拉函数+容斥原理).docx
ACM题库,一些题目和答案,以及解题报告,传上来共享
hdu 3341(ac自动机+状态压缩) 题意:容易理解... 思路:首先一开始容易想到要用到dp,开设一个dp[41][41][41][41][501]的数组来解决,但是明显内存已经超出范围了,于是就想如何减少内存呢?只要知道A、T、C、G其中...
杭电OnlineJudge 200-2099的解题报告
acm hdu as easy as a+b
本人准备2020年保研机试时刷的题目(虽然最后机试取消了,...来自某中流985,在HDU和vjudge平台上大概刷了400道。本文件地图(excel表格)包含了绝大部分我刷过的题目,笔记中具有思路、代码、总结和心得。 大佬勿入!
Problem Description 话说,经过了漫长的一个多月,小明已经成长了许多,所以他改了一个名字叫“大明”。 这时他已经不是那个只会做100以内加法的那个“小明”了,现在他甚至会任意长度的正小数的加法。...
从简单入门到偏中等的几个题,线段树很灵活,主要懂了lazy操作,其他的自己yy吧。
(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数(HDUACM2010版_08)母函数
300+ AC 代码 。 大数 , 线段树 , 字符串 , dp.....
HDU的1250,主要是利用高精度加法,但是代码有点繁琐,效率不是很高
2、new做两件事,一是分配内存,二是调用类的构造函数 3、new建立的是一个对象,而malloc分配的是一块内存 4、new/delete是保留字,不需要头文
HDU1059的代码
杭电ACMhdu1163
hdu1001解题报告
hdu 1574 passed sorce
HDU的一题........HDU DP动态规
hdu acm 教案 搜索入门 hdu acm 教案 搜索入门
hdu2101AC代码