关键词：
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5297；
题意：给出n和r，求数列Y的第n个元素是多少。其中数列Y是正整数数列去除a^b(2<=b<=r)后的数
分析：
我的天啊，出一个数n，则1~n以内的正整数必定会有被去除的（假设被去除x1个），则这n个数中只有（n-x1）个数在Y数列中；如果想得到n个数在Y数列中，那么我们至少要在这n个数后面加上x1个数，设n1=n+x1，则在1~n1内的数有多少在Y数列中呢（假设有m个在Y数列中，去除了x2个）？如前面所说，在1~n1内的数最多有n个数在Y数列中（即m<=n），此时判断m与n是否相等。如果相等，则Y数列中第n个数为（n+x1）；如果不相等，则继续在（n+x1）数后面再加x2个数，继续判断……一直加到某个数M，使得1~M内的数在Y数列中刚好有n个。关键在于如何求解在小于n的数里内有多少个数可以表示为a^b；
这时就要用到容斥原理了；
代码如下：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <cmath>
#include <algorithm>
#include <iostream>
#include <functional>
using namespace std;
int a[]={-2,-3,-5,-7,-11,-13,-17,-19,-23,-29,-31,-37,-41,-43,-47,-53,-59,-61,-67};
//选择负数是方便进行容斥原理
vector<int>G;
void get_su(int r){
for(int i=0;abs(a[i])<=r;i++){
int s=G.size();
for(int j=0;j<s;j++){
if(abs(a[i]*G[j])<=63){
G.push_back(a[i]*G[j]);
}
}
G.push_back(a[i]);
}
}
//把小于r的数进行容斥
long long sm(long long x){
if(x==1)return 0;
int s=G.size();
long long ans=x;
for(int i=0;i<s;i++){
long long tmp=(long long)(pow(x+0.5,1/(double)(abs(G[i]))))-1;
if(G[i]<0)ans-=tmp;
else ans+=tmp;
}
return ans-1;
}
//求解每一步的值
int main(){
int t;
scanf("%d",&t);
while(t--){
int r;
long long n;
scanf("%I64d%d",&n,&r);
G.clear();
get_su(r);
long long tmp;
long long ans=n;
while(1){
tmp=sm(ans);
// cout<<tmp<<endl;
if(tmp==n)break;
ans+=n-tmp;
}
printf("%I64d
",ans);
}
return 0;
}
hdu4135(容斥原理)
Co-primeTimeLimit:2000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):4090 AcceptedSubmission(s):1619ProblemDescriptionGivena 查看详情
hdu1796howmanyintegerscanyoufind容斥原理
Description NowyougetanumberN,andaM-integersset,youshouldfindouthowmanyintegerswhicharesmallthanN,thattheycandividedexactlybyanyintegersintheset.Forexample,N=12,andM-integersetis{2,3},sothe 查看详情
hdu2461rectangles#容斥原理
...，这样子效率更高，否则的话，这道题就TLE了。 根据容斥原理，先把每个小长方形的面积加上，然后看有没有与该小长方形相交的，用dfs实现，当相交面积为0时，则不进行dfs，且同样遵循奇加偶减（但代码里因为是以第二 查看详情
hdu5514容斥原理
...。问这些青蛙踩过的石子的编号总和是多少？tags： 容斥经典题。对m分解因子，对每个因子求贡献。#include<bits/stdc++.h>usingnamespacestd;#pragmacomment(linker,"/S 查看详情
hdu5514容斥原理(代码片段)
FrogsTimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/65536K(Java/Others)TotalSubmission(s):4843 AcceptedSubmission(s):1605ProblemDescriptionThereare& 查看详情
hdu5468(dfs序+容斥原理)
PuzzledElenaTimeLimit:5000/2500MS(Java/Others) MemoryLimit:131072/131072K(Java/Others)TotalSubmission(s):1162 AcceptedSubmission(s):339ProblemDescriptionS 查看详情
hdu5468(dfs序+容斥原理)
PuzzledElenaTimeLimit:5000/2500MS(Java/Others) MemoryLimit:131072/131072K(Java/Others)TotalSubmission(s):1247 AcceptedSubmission(s):370ProblemDescriptionS 查看详情
容斥原理——hdu2841(代码片段)
记得要开ll/*莫比乌斯反演模板题，也可以直接算phi来做容斥的解法求x[1..m],在[1,n]中和其互质的数的个数即可那么就是n-和x不互质的数个数即可*/#include<bits/stdc++.h>#include<vector>usingnamespacestd;#definemaxn100005#definelllonglongvector&... 查看详情
hdu4407sum(容斥原理)
...题能够转化为求[1,R]之间与p不互素的数的和，这个能够用容斥原理来做，然后用区间和减去这个值就是答案，这是静态的做法。假设有改动的话 查看详情
hdu4390numbersequence（容斥原理+组合计数）
HDU4390题意：大概就是这样。不翻译了：Givenanumbersequenceb1,b2…bn.Pleasecounthowmanynumbersequencesa1,a2,...,ansatisfytheconditionthata1?a2?...?an=b1?b2?…?bn(ai,bi>1).思路：我们能够确定一件事：等号两边由同样数量的质因子组成。假设ai能够等于1，... 查看详情
hdu1796howmanyintegerscanyoufind(容斥原理）(代码片段)
...能整除m数组中的一个数(1<=n<=10^18.m<=20)题解这题是容斥原理基本模型。枚举n中有多少m中元素的个数，在结合LCM考虑容斥。1#include<iostream>2#include<cstring>3#include<cstdio>4#include< 查看详情
hdu4153（容斥原理求质数）(代码片段)
传送门 ac代码：#include<bits/stdc++.h>#defineper(i,a,b)for(inti=a;i<=b;i++)usingnamespacestd;typedeflonglongll;//#defineintlonglongconstllinf=2333333333333333LL;constdoubleeps=1e-8;intread()c 查看详情
hdu6021mglovesstring（枚举+容斥原理）
MGlovesstring Accepts:30 Submissions:67 TimeLimit:2000/1000MS(Java/Others) MemoryLimit:262144/262144K(Java/Others)问题描述MGMG是一个很忙碌的男孩子。今天他沉迷于这样一个问题：对于一个长度为NN的由小写英文字母构成的随机字符串，当... 查看详情
hdu-6314matrix（广义容斥原理）(代码片段)
...//blog.csdn.net/IcePrincess_1968/article/details/81255138重点在于计算容斥系数。 #include<iostream>#i 查看详情
hdu4135co-prime容斥原理
Co-primeTimeLimit:2000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):626 AcceptedSubmission(s):234 ProblemDescriptionGi 查看详情
[容斥原理]hdu1796howmanyintegerscanyoufind
...出现反复比方例子6就会被反复算 这时候我们就须要容斥原理了加上一个数的减去两个数的。。这里要注意了两个数以上的时候是求LCM而不是简单的相乘！代码：#include"stdio.h" 查看详情
hdu5768lucky7（crt+容斥原理）
...小的x值，那么这样子我们就可以对所有的aibi选取方式做容斥，得到xmod 查看详情
hdu4059：thebossonmars（数学公式+容斥原理）
http://acm.hdu.edu.cn/showproblem.php?pid=4059题意：给出一个n，求1~n里面与n互质的数的四次方的和是多少。思路；不知道1~n的每个数的四次方的求和公式。看的是这篇：http://blog.csdn.net/acm_cxlove/article/details/7434864。求和公式：(1^4+2^4+…... 查看详情