一个数n和一个包含m个数的集合,让你求小于n的有多少个数能整除这m个数中的任意一个
import java.util.Scanner; public class Main { static long nums[]=new long[25],m,n,sum; static int count; static long gcd(long a,long b) { return b==0?a:gcd(b, a%b); } static void dfs(int start,long c,long lcm) { lcm=lcm/gcd(lcm, nums[start])*nums[start];//最小公倍数 if(c%2==1) sum+=(n-1)/lcm; else sum-=(n-1)/lcm; for(int j=start+1;j<count;j++) { dfs(j, c+1, lcm); } } public static void main(String[] args) { Scanner scanner=new Scanner(System.in); while(scanner.hasNext()) { n=scanner.nextLong(); m=scanner.nextLong(); count=0; for(int i=0;i<m;i++) { long x=scanner.nextLong(); //注意数据里有0的情况,应该舍去,不影响结果 if(x==0)continue; else nums[count++]=x; } sum=0; for(int i=0;i<count;i++) { dfs(i,1,nums[i]); } System.out.println(sum); } } }