首页 > ACM题库 > HDU-杭电 > hdu 2731 Consecutive Digits-数论应用-[解题报告]C++
2014
02-14

hdu 2731 Consecutive Digits-数论应用-[解题报告]C++

Consecutive Digits

问题描述 :

As a recruiting ploy, Google once posted billboards in Harvard Square and in the Silicon Valley area just stating “{first 10-digit prime found in consecutive digits of e}.com”. In other words, find that 10-digit sequence and then connect to the web site― and find out that Google is trying to hire people who can solve a particular kind of problem. Not to be outdone, Gaggle (a loosy-goosy fuzzy logic search firm), has devised its own recruiting problem. Consider the base 7 expansion of a rational number. For example, the first few digits of the base 7 expansion of 1/510 = 0.12541…7,33/410 = 11.15151…7, and 6/4910 = 0.06000…7, From this expansion, find the digits in a particular range of positions to the right of the "decimal" point.

输入:

The input file begins with a line containing a single integer specifying the number of problem sets in the file. Each problem set is specified by four base 10 numbers on a single line, n d b e, where n and d are the numerator and
denominator of the rational number and 0 ≤ n ≤ 5,000 and 1 ≤ d ≤ 5,000. b and e are the beginning and ending positions for the desired range of digits, with 0 ≤ b,e ≤ 250 and 0 ≤ (e-b) ≤ 20. Note that 0 is the position immediately to the right of the decimal point.

输出:

The input file begins with a line containing a single integer specifying the number of problem sets in the file. Each problem set is specified by four base 10 numbers on a single line, n d b e, where n and d are the numerator and
denominator of the rational number and 0 ≤ n ≤ 5,000 and 1 ≤ d ≤ 5,000. b and e are the beginning and ending positions for the desired range of digits, with 0 ≤ b,e ≤ 250 and 0 ≤ (e-b) ≤ 20. Note that 0 is the position immediately to the right of the decimal point.

样例输入:

4
1 5 0 0
6 49 1 3
33 4 2 7
511 977 122 126

样例输出:

Problem set 1: 1 / 5, base 7 digits 0 through 0: 1
Problem set 2: 6 / 49, base 7 digits 1 through 3: 600
Problem set 3: 33 / 4, base 7 digits 2 through 7: 151515
Problem set 4: 511 / 977, base 7 digits 122 through 126: 12425

int main()
{
	int cases, x = 1;
	cin>>cases;
	while (cases--) {
		int a, b, c, d;
		cin>>a>>b>>c>>d;
		printf("Problem set %d: %d / %d, base 7 digits %d through %d: ", x++, a, b, c, d);
		int i;
		a %= b;
		for (i = 0; i <= d; ++i) {
			a *= 7;
			if (i >= c) {
				printf("%d", a / b);
			}
			a %= b;
		}
		printf("\n");
	}
    return 0;
}

解题转自:http://blog.csdn.net/famousdt/article/details/7431366


  1. “再把所有不和该节点相邻的节点着相同的颜色”,程序中没有进行不和该节点相邻的其他节点是否相邻进行判断。再说求出来的也不一样是颜色数最少的

  2. 第二个方法挺不错。NewHead代表新的头节点,通过递归找到最后一个节点之后,就把这个节点赋给NewHead,然后一直返回返回,中途这个值是没有变化的,一边返回一边把相应的指针方向颠倒,最后结束时返回新的头节点到主函数。

  3. Thanks for taking the time to examine this, I really feel strongly about it and love studying a lot more on this topic. If possible, as you acquire experience