NC16513. 无关(relationship)
描述
若一个集合A内所有的元素都不是正整数N的因数，则称N与集合A无关。
输入描述
输入数据共两行：
第一行三个正整数L,R,k，意义如“题目描述”。
第二行k个正整数，描述集合A，保证k个正整数两两不相同。
输出描述
输出数据共一行：
第一行一个正整数表示区间[L,R]内与集合A无关的正整数的个数
示例1
输入:
1 10 4 2 3 5 7
输出:
1
示例2
输入:
2 10 4 2 3 5 7
输出:
0
说明:
对于30%的数据：1<=L<=R<=10^6C++14(g++5.4) 解法, 执行用时: 64ms, 内存消耗: 504K, 提交时间: 2020-05-06 16:28:47
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[22];
ll l,r,k;
ll dfs(int i,ll x){
if(i>k) return x;
else return dfs(i+1,x)-dfs(i+1,x/a[i]);
}
int main(void)
{
cin>>l>>r>>k;
for(int i=1;i<=k;i++)cin>>a[i];
cout<<dfs(1,r)-dfs(1,l-1);
}
C++(clang++11) 解法, 执行用时: 21ms, 内存消耗: 504K, 提交时间: 2021-04-16 10:48:09
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int a[30];
ll n,l,r;
ll dfs(int i,ll x){
if(i==n)return x;
return dfs(i+1,x) - dfs(i+1,x/a[i]);
}
int main(){
cin>>l>>r>>n;
for(int i=0;i<n;i++) cin>>a[i];
cout<<dfs(0,r)-dfs(0,l-1)<<endl;
}