首页 > 代码库 > COGS 513 八

COGS 513 八

2024-09-10 17:28:02   219人阅读

513. 八

http://www.cogs.pro/cogs/problem/problem.php?pid=513

★☆   输入文件：eight.in   输出文件：eight.out   简单对比
时间限制：1 s   内存限制：128 MB

【问题描述】

八是个很有趣的数字啊。八=发，八八=爸爸，88=拜拜。当然最有趣的还是8用二进制表示是1000。怎么样，有趣吧。当然题目和这些都没有关系。 
某个人很无聊，他想找出[a,b]中能被8整除却不能被其他一些数整除的数。

【输入文件】

第一行一个数n，代表不能被整除的数的个数。第二行n个数，中间用空格隔开。第三行两个数a，b，中间一个空格。

【输出文件】

一个整数，为[a,b]间能被8整除却不能被那n个数整除的数的个数。

【样例输入】 
eight.in

3
7764 6082 462
2166 53442
【样例输出】

eight.out 
6378

【数据规模】 
对于30%的数据， 1≤n≤5，1≤a≤b≤100000。 
对于100%的数据，1≤n≤15，1≤a≤b≤10^9，N个数全都小于等于10^4大于等于1。

 

容斥原理

全集Z=能被8整除的数

性质p1为能被n1整除，p2为不能被8整除，能被n2整除……

ans=Z中不包含任意性质p的数

这些数都有一个前提：在Z中，所以最小公倍数初值为8

 

dfs过程中遇到的障碍：

求好几个数的lcm时，

没有必要for枚举几个数，在枚举哪几个数

容斥原理所有项的加加减减都是集合的所有子集

所以dfs时只需分这个数加不加入这个子集即可

这样计算n个数的lcm时，还可利用计算的n-1个数的lcm结果

 

递归式写法:

#include<cstdio>using namespace std;int n,ans;long long a,b,f[10001];int cal(long long m){    return b/m-(a-1)/m;}long long gcd(long long x,long long y){    return y ? gcd(y,x%y):x;}long long lcm(long long x,long long y){    return x*y/gcd(x,y);}void dfs(int now,long long num,int sum){    if(now==n+1)    {        int s=cal(num);        if(sum%2) ans-=s;        else ans+=s;        return;    }    long long next=lcm(num,f[now]);    dfs(now+1,next,sum+1);    dfs(now+1,num,sum);}int main(){    freopen("eight.in","r",stdin);    freopen("eight.out","w",stdout);    scanf("%d",&n);    for(int i=1;i<=n;i++) scanf("%lld",&f[i]);    scanf("%lld%lld",&a,&b);    dfs(1,8,0);    printf("%d",ans);}

 

非递归写法：

利用二进制生成子集

#include<cstdio>using namespace std;int n,ans;long long a,b,f[10001];int cal(long long m){    return b/m-(a-1)/m;}long long gcd(long long x,long long y){    return y ? gcd(y,x%y):x;}long long lcm(long long x,long long y){    return x*y/gcd(x,y);}int main(){    freopen("eight.in","r",stdin);    freopen("eight.out","w",stdout);    scanf("%d",&n);    for(int i=0;i<n;i++) scanf("%lld",&f[i]);    scanf("%lld%lld",&a,&b);    int sum=1<<n,cnt;    ans=b/8-(a-1)/8;    long long lcmm;    for(int i=1;i<sum;i++)    {        cnt=0;lcmm=8;        for(int j=0;j<n;j++)          if(i&(1<<j)) lcmm=lcm(lcmm,f[j]),cnt++;        if(cnt&1) ans-=b/lcmm-(a-1)/lcmm;        else ans+=b/lcmm-(a-1)/lcmm;    }    printf("%d",ans);}

 

COGS 513 八


联系
我们