Lucky Number zju 3233 解题报告

Mon, 31 Aug 2009 01:05:54 +0000

题意：哇他是这个猥琐男喜欢M mm，而M mm似乎想要故意为难他一下，所以她给了哇他是一串BLN和一串BUN，以及一个给定Luck number的定义:一个数是Lcuk number当且仅当这个数可以被整除BLN中的任意一个而不整除BUN中的任意一个。
现在M mm给了哇他是一个区间[low, high]，让哇他是在这个区间里面找出一个数来，如果这个数满足Luck number的定义，那么M mm就嫁个他。
现在哇他是想要知道这个区间里面有多少个满足Luck number定义的数。

看完题后的第一感觉就是容斥原理，具体容斥原理的资料可以找本组合数学的书看看。

不过一开始对于“不整除BUN中的任意一个”这句话有点疑惑，其实这句话的方面就是“去掉整除BUN中所有数的数”这样我们就很好理解了，我们把Luck number的定义看作是两个条件：
1.求出所有能够整除BLN的数
2.求出所有能够整除BLN但是又不整除所有BUN的数（不整除所有BUN的数，其实就是不整除BUN的最小公倍数）
我们要求的Luck number实际上就是：满足条件1的数减去满足条件2的数

根据容斥原理求解某个数的因子个数，我们可以很轻松的求解出某个区间里面所有满足条件1的数，那么条件2我们怎么求呢？其实条件2我们同样是运用容斥原理来求解，我们只需要将BLN中所有的数的组合乘以BUN中的最小公倍数运用一次容斥原理就可以求解出满足条件2的数了，求解出来的两个答案相减，over！

这个题目WA了N次，问题就出在我构造的使用容斥原理求解因子个数的程序的预处理上，一开始我写程序的时候包含有一个排序操作预处理数组的，后来修改程序过程中删除了，但是我在构造数据的时候一直按照从小到大的循序构造的，因此一直没有找出错误来……

#include
#include

//zju只能够使用long long
typedef long long int64;
int64 INF;
int64 nbln, nbun, left, right, bln[20], bun[510], sum;

//a b的最大公约数
int64 gcd(int64 a, int64 b)
{
        if(b == 0) return a;
        else return gcd(b, a%b);
}

//a b的最小公倍数数，如果两个数的最小公倍数超过了表达范围则返回0
int64 lcm(int64 a, int64 b)
{
        int64 t;
        if(a == 0 || b == 0) return 0;
        t = gcd(a, b);
        t = a/t;
        if(INF/t < b) return 0;
        return t*b;
}

//容斥原理求解因子个数的数，递归的求解
void rong(int64 a, int s, int l)
{
        int i;
        int64 t;
        for(i=s; i        {
                t = lcm(a, bln[i]);
                if(t==0 || a > right) return;
                if(l%2 == 1) sum -= (right/t-left/t);
                else sum += (right/t-left/t);
                rong(t, i+1, l+1);
        }
}

int  main()
{
        int i, j, k;
        int64 t, ans;
        INF = (1<<31);
        INF = (INF<<31);
        INF = (INF<<1)-1;
        while(scanf("%lld%lld%lld%lld", &nbln, &nbun, &left, &right) && nbln+nbun+left+right)
        {
                left--;
                for(i=0; i                for(i=0; i                //容斥原理的预处理
                for(i=0; i                {
                        for(j=i+1; j                        {
                                if(bln[i] > bln[j])
                                {
                                t = bln[i];
                                bln[i] = bln[j];
                                bln[j] = t;
                                }
                        }
                }
                sum = 0;
                //满足条件1的数
                rong(1, 0, 0);
                t = 1;
                for(i=0; i                {
                        t = lcm(t, bun[i]);
                        if(t == 0) break;
                }
                ans = sum;
                sum = 0;
                //满足条件2的数
                rong(t, 0, 0);
                ans -= sum;
                printf("%lld\n", ans);
        }
        return 0;
}

PKU ACM 2356

Fri, 26 Sep 2008 13:13:57 +0000

原题链接：2356
题意：
让我们从给出的N个数中找出few个数，使得这few个数的和可以整除N，如果不存在few个这样的数，那么就输出0；如果存在这样的数，那么就输出这few个数。

题意很清楚，但是我们看看规模就知道如果使用枚举的办法的话，那么操作起来将会非常的困难。下面我们就来看一下通过抽屉原理的证明：

证明：
输入有N个自然数，将这N个自然数从第一个开始取连续和可以得到N个和，然后将这N个和对N取模可以得到N个模，那么可以分为以下两种情况：
1.至少存在一个余数为0（假设为前i个数的和），那么前面i个数的和必然可以被N整除。
2.其中不存在余数为0的情况，那么根据抽屉原理这N个数中存在至少2个数的余数相同（假设这两个数分别为i，j），那么我们就可以确定在这两个余数相同之间的数的和就必然被N整除（既 (sum[j]-sum[i])%N==0) ）。

这个题目里面我也有一些疑问，那就是自然数到底是从哪里开始的？

代码见内页

Tags - acm , pku , 2356 , 抽屉原理

卡喀の博客

Lucky Number zju 3233 解题报告

PKU ACM 2356