当前位置:编程学习 > C/C++ >>

Hoj 2577 Simple Computing II

基本思想都是用容斥原理。

hoj 2576 给出一组数x1...xn,问从1到m中能有多少个数能够整除这组数中的至少一个数。

hoj 2577 给出一组数x1...xn,问从1到m中能有多少个数能够整除这组数中的唯一的数。

其实原理都是一样的,hoj 2576所求的情况类似于下图:

 \


所有被蓝线覆盖的区域大小为:x1 + x2 + x3 - x1*x2 - x1*x3 - x2*x3 + x1*x2*x3;

即奇加偶减。

hoj 2577对应的情况类似于下图:

 \


蓝线覆盖的区域为:x1 + x2 + x3 - 2*(x1*x2 - x1*x3 - x2*x3) + 3(x1*x2*x3);

即:仍然是奇加偶减,但是要乘以相应的等于乘数个数的系数。

hoj 2577的代码:


[cpp]
#include <iostream>  
#include <stdio.h>  
#include <stdlib.h>  
#include <string.h>  
#include <math.h>  
#include <vector>  
using namespace std; 
 
long long x[12]; 
 
long long gcd(long long a,long long b) 

    if(b == 0) 
    { 
        return a; 
    } 
    else 
    { 
        return gcd(b,a%b); 
    } 

 
int main() 

#ifndef ONLINE_JUDGE  
    freopen("in.txt","r",stdin); 
#endif  
    int t; 
    scanf(" %d",&t); 
    while(t--) 
    { 
        long long n,m; 
        long long sum = 0; 
        scanf(" %lld %lld",&n,&m); 
 
        for(long long i=0;i<n;i++) 
        { 
            scanf(" %lld",&x[i]); 
        } 
        for(long long i = 1;i<(1<<n);i++) 
        { 
            long long s = 1; 
            long long bits = 0; 
            for(long long j=0;j<n;j++) 
            { 
                if(i &(1<<j)) 
                { 
                    bits++; 
                    s *= x[j]/gcd(s,x[j]); 
                } 
            } 
            long long temp = m/s; 
            //bits是奇数时  
            if(bits&1) 
            { 
                sum +=temp*bits; 
            } 
            else 
            { 
                sum -=temp*bits; 
            } 
        } 
        printf("%lld\n",sum); 
 
    } 

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <vector>
using namespace std;

long long x[12];

long long gcd(long long a,long long b)
{
    if(b == 0)
    {
        return a;
    }
    else
    {
        return gcd(b,a%b);
    }
}

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
#endif
    int t;
    scanf(" %d",&t);
    while(t--)
    {
        long long n,m;
        long long sum = 0;
        scanf(" %lld %lld",&n,&m);

        for(long long i=0;i<n;i++)
        {
            scanf(" %lld",&x[i]);
        }
        for(long long i = 1;i<(1<<n);i++)
        {
            long long s = 1;
            long long bits = 0;
            for(long long j=0;j<n;j++)
            {
                if(i &(1<<j))
                {
                    bits++;
                    s *= x[j]/gcd(s,x[j]);
                }
            }
            long long temp = m/s;
            //bits是奇数时
            if(bits&1)
            {
                sum +=temp*bits;
           

补充:软件开发 , C++ ,
CopyRight © 2012 站长网 编程知识问答 www.zzzyk.com All Rights Reserved
部份技术文章来自网络,