首页 > ACM题库 > HDU-杭电 > hdu 3880-lucky numbers-枚举-[解题报告]hoj
2015
04-13

hdu 3880-lucky numbers-枚举-[解题报告]hoj

#include <stdio.h>
#include <stdlib.h>
#include <string.h>


int main(){
	__int64 i, j, k;
	__int64 a, b, M;
	while(scanf("%I64d%I64d%I64d", &a, &b, &M) != EOF){
		if (a > b){
			k = a;
			a = b;
			b = k;
		}
		if (b == 1){
			k = M;
		}else{
			k = 0;
			j = 1;
			for (i = b; M / i > 0; i = i * b){
				k += j * M / i;
				j = -j;
			}
		}
		printf("%I64d\n", k);
	}
    system("pause");
    return 0;
}


/***************
结论是猜的,开始题目还看错了。。。
暴力的又连番写错。。。好久俩程序才对上。。。
其实这结论,稍分析,再猜一猜,还是容易猜到的,连我这个没啥找规律细胞的

,都能找到。。。表示自己很惊奇。。。
M/b是上界,当m1*a=m2*b时,又可以省M/ab个,但其中有些是不能省的,再加上

M/ab - M/bb,表达不清楚。。反正类似这样的情况,加加减减的。。。我也没搞

清楚。。。
***************/

Problem Description
Lucy and Lily are twin sisters. Mr. Smith, their father, a mathematician, gave each of them a lucky number (positive integer) when they were born, and the two lucky numbers have only one common divisor, of course, it is 1.

Mr. Smith is extremely excited to see that his two little children are so interested in math and both of them show amazing talent. Mr. Smith now will teach the two little girls to do multiplication. He wants to start with the two lucky numbers a and b.

Mr. Smith will write a set of positive integers (we call it SetA) such that for any positive integer m, we can find m*a or m*b in SetA. Because Lucy and Lily can only count from 1 to M, so if m*a or m*b is larger than M, Mr. Smith will ignore m.

Mr. Smith wants to write least numbers.
So help him to figure out the minimum number of elements in SetA.
For example the lucky numbers are 3 and 2, and M is 7.
Mr. Smith could write 3,6,2,4. He could also write only 3,6,4 or 3,6 or 2,4. But in no way could he write only one number contain both (1*3 or 1*2) and (2*3 or 2*2).

Input
The input has multiple cases, process to EOF. There are about 10000 cases.
Each case contains a line with 3 positive integers: a b M as described above.
We ensure the greatest common divisor of a and b is 1.
M, a, b are all fit 32bit integers.

Output
For each test case, output a line with only one integer, the minimum number of elements in SetA.

Sample Input
3 2 7
4 3 8

Sample Output
2
2

版权声明:本文为博主原创文章,未经博主允许不得转载。


  1. [email protected]

  2. 第二块代码if(it != mp.end())应改为if(it != mp.end() && (i+1)!=(it->second +1));因为第二种解法如果数组有重复元素 就不正确

  3. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }