容斥原理,欧拉函数

作者: 关于计算机  发布:2019-11-15

hdu4002 Find the maximum 欧拉函数

//求小于N且n/phi(x)最大的n如果有多少个,输出最小的
//phi(x) = x*(1-1/p1)*(1-1/p2)*(1-1/p3)....
//要使得x/phi(x) 最大,即使得(1-1/p1)*(1-1/p2)*(1-1/p3)....最小
//又p1, p2 , p3 , ....
//全为素数因子,所以能够对枚举全数素数因子乘积,
//打表后找小于等于n的数
#include
#include
#include
using namespace std ;
const int maxn = 1010;
char str[maxn] ;
int num[maxn][maxn] ;
int num_1[maxn] ;
int len[maxn] ;
int isp[maxn] ;
int prime[maxn] ;
int set()
{
memset(isp , 0 ,sizeof(isp)) ;
isp[1] = 1;
for(int i = 4;i < maxn;i+=2)
isp[i] = 1;
for(int i = 3;i < maxn;i++)
{
if(isp[i])continue ;
for(int j = i*i;j < maxn;j+=i)
isp[j] = 1;
}
int j = 0 ;
for(int i = 1;i < maxn;i++)
if(!isp[i])prime[++j] = i ;
return j ;
}
bool cmp(int len_1 , int len_2 , int pos)
{
if(len_1 > len_2)return 0 ;
if(len_2 > len_1)return 1 ;
for(int i = len_1 ;i > 0;i--)
{
if(num_1[i] > num[pos][i])
return 0 ;
if(num_1[i] < num[pos][i])
return 1 ;
}
return 0 ;
}
void init()
{
int sum = set() ;
num[0][1] = 1;
len[0] = 1;
for(int i = 1;;i++)
{
int c = 0 ;
len[i] = len[i-1] ;
for(int j = 1;j <= len[i];j++)
{
num[i][j] = prime[i]*num[i-1][j] ;
num[i][j] += c ;
c = num[i][j]/10 ;
num[i][j] %= 10 ;
}
while(c)
{
num[i][++len[i]] = c%10 ;
c/=10 ;
}
if(len[i] > 100)break;
}
}
int main()
{
init() ;
int T ;
scanf("%d" , &T) ;
while(T--)
{
scanf("%s" , str) ;
int len_1 = strlen(str) ;
for(int i = len_1 - 1;i >= 0 ;i--)
num_1[len_1 - i] = str[i] - '0' ;
int pos = 1;
while(!cmp(len_1 , len[pos] , pos))pos++ ;
for(int i = len[pos-1];i >= 1;i--)
printf("%d" , num[pos-1][i]) ;
puts("") ;
}
}

Find the maximum 欧拉函数 //求小于N且n/phi(x)最大的n倘诺有八个,输出最小的 //phi(x) = x*(1-1/p1)*(1-1/p2)*(1-1/p3).... //要使得x/phi(x) 最大,即使...

hdu3388Coprime 二分+容斥原理

//找第k个和n,m互质的数
//由容斥原理可得
//在[1,x]界定内且与n不互质的数的个数为:
//对于全部的n的素数因子:和五个素数因子不互质的个数-四个素数因子相乘的个数+多少个素数因子相乘的个数-.....
//对于x越大,在[1 , x]限制内的与n,m互质的数越来越多,所以存在单调性,能够用二分找到适逢其会有k个数和n,m互质
#include
#include
#include
#include
using namespace std ;
typedef __int64 ll ;
const int maxn = 100010 ;
const int inf = 1e9 ;
mapma ;
ll p[maxn] ;
int len ;
void getprime(ll n)
{
for(int i = 2;i*i <= n;i++)
{
if(n%i == 0 && !ma[i])
{
p[++len] = i ;
ma[i] = 1;
}
while(n%i == 0)n/=(ll)i ;
}
if(n > 1 && !ma[n]){p[++len] = n;ma[n]=1;}
}
ll dfs(int pos , ll n)
{
ll ans = 0 ;
for(int i = pos ;i <= len ;i++)
ans += n/p[i] - dfs(i+1 , n/p[i]) ;
return ans ;
}
ll find(ll l , ll r , ll num )
{
while(l <= r)
{
ll mid = (l+r) >> 1 ;
if((mid - dfs(1 , mid)) < num)
l = mid + 1 ;
else r = mid - 1;
}
return l ;
}
int main()
{
// freopen("in.txt","r",stdin) ;
// freopen("out.txt","w" ,stdout) ;
int T ;int cas = 0 ;
int n , m ;int k ;
scanf("%d" , &T) ;
while(T--)
{
scanf("%d%d%d" ,&n , &m , &k) ;
len = 0 ;
ma.clear() ;
getprime((ll)(n));
getprime((ll)(m));
ll ans = find(1 , (ll)inf*(ll)inf, (ll)k);
printf("Case %d: " , ++cas) ;
printf("%I64dn" , ans) ;
}
return 0;
}

二分+容斥原理 //找第k个和n,m互质的数 //由容斥原理可得 //在[1,x]范围内且与n不互质的数的个数为: //对于具备的n的素数因子...

本文由今晚开什么码发布于关于计算机,转载请注明出处:容斥原理,欧拉函数

关键词:

上一篇:线段树区间更新,线段树专项论题
下一篇:没有了