大家好，又见面了，我是全栈君，今天给大家准备了Idea注册码。
//设置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 ;
}
//利用已知的容斥原理
//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.net/117231.html原文链接：https://javaforall.net
