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;
}