例题:HDU4135 HDU2841,HDU1695,HDU3501
HDU4135例题博客
利用容斥原理,先求不互质的个数ans,最后结果n−ans。
先将m分解质因子。存到p数组里。
假如m有 2,3,5质因子,那么2, 3, 5的倍数与m都不互质,但是会有重复。用容斥原理算出正确的即可。
k / 2 + k / 3 + k / 5 - k / (2 * 3) - k / (3 * 5) - k / (2 * 5) + k / (2 * 3 * 5)
出现奇数次的加,出现偶数次的减。
代码枚举所有质因子的组合时用二进制枚举。
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define pll pair<int, int>
#define mk(x, y) make_pair(x, y)
#define d(x) cout<<x<<endl
const int N = 1e4 + 5;
const ll mod = 1e9 + 7;
ll n, m, cnt;
ll p[N];
void get_factor(){ // m 比较大的话可以先打出来素数表再求
cnt = 0;
for(int i = 2; i * i <= m; i++){
if(m % i == 0){
p[cnt++] = i;
while(m % i == 0)
m /= i;
}
}
if(m > 1)
p[cnt++] = m;
}
ll solve(){
ll ans = 0;
for (int i = 1; i < (1 << cnt); i++){ // 二进制枚举质因子所有组合
ll tmp = 1, t = 0;
for(int j = 0; j < cnt; j++){
if((1<<j)&i){ // 如果第 j 位为一
tmp *= p[j];
t++;
}
}
ans += (t & 1 ? n / tmp : -n / tmp); // 奇加偶减
}
return n - ans;
}
int main(){
cin >> n >> m;
get_factor();
d(solve());
return 0;
}
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e6+100;
//求1~n中与m互质的数的个数
/*
利用容斥原理,先求不互质的个数 ans,最后结果 n-ans。
先将 m分解质因子。存到 p数组里。
假如 m 有 2,3,5质因子,那么2, 3, 5的倍数与 m都不互质,但是会有重复。用容斥原理算出正确的即可。
k / 2 + k / 3 + k / 5 - k / (2 * 3) - k / (3 * 5) - k / (2 * 5) + k / (2 * 3 * 5)
出现奇数次的加,出现偶数次的减。
代码枚举所有质因子的组合时用二进制枚举。
*/
ll n,m,cnt,p[maxn];
void get_factor(ll m){
cnt=0;
for(int i=2;i*i<=m;i++){
if(m%i==0){
p[cnt++]=i;
while(m%i==0){
m/=i;
}
}
}
if(m>1){
p[cnt++]=m;
}
}
ll solve(ll n){
ll ans=0;
for(int i=1;i < (1 << cnt);i++){
ll temp=1,t=0;
for(int j=0;j<cnt;j++){
if((1<<j)&i){
temp*=p[j];
t++;
}
}
if(t%2==1){
ans+=n/temp;
}
else{
ans-=n/temp;
}
}
return n-ans;
}
int main(){
scanf("%d%d",&n,&m);
get_factor(m);//分解质因子
cout<<solve(n)<<endl;
}
原文链接: https://www.cnblogs.com/lipu123/p/14187000.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/206474
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!