hdu1796 How many integers can you find

大家好，又见面了，我是全栈君。

//设置m，Q小于n可以设置如何几号m随机多项整除 //利用已知的容斥原理 //ans = 数是由数的数目整除 – 数为整除的两个数的数的最小公倍数 + 由三个数字。。。 #include<cstdio> #include<cstring> #include<iostream> using namespace std ; const int maxn = 110 ; typedef __int64 ll ; int a[maxn] ; int len ; int n , m ; ll gcd(ll a , ll b) { if(b == 0) return a ; return gcd(b, a%b) ; } int dfs(int pos , ll lcm) { int ans = 0 ; for(int i = pos ;i <= len;i++) { ll lcm_n = lcm*a[i]/gcd(lcm , a[i]) ;//最小公倍数可能会爆int，被坑了一下 ans += (n-1)/lcm_n – dfs(i+1 , lcm_n) ; } return ans ; } int main() { while(~scanf(“%d%d” , &n , &m)) { len = 0 ; for(int i = 1;i <= m;i++) { int t ; scanf(“%d” , &t) ; if(!t) continue ;//可能会有0 a[++len] = t ; } int ans = dfs(1 , 1) ; printf(“%d\n” , ans) ; } return 0 ; }

版权声明：本文博客原创文章，博客，未经同意，不得转载。

发布者：全栈程序员栈长，转载请注明出处：https://javaforall.cn/117231.html原文链接：https://javaforall.cn