10518 - How Many Calls?

[misof]

I need some i/o.

Suman.

In:

Code: Select all

0 1
0 2
0 3
0 4
0 5
0 7777
0 10000
1 1
1 2
1 3
1 4
1 5
1 7777
1 10000
987654321987654321 1
987654321987654321 2
987654321987654321 3
987654321987654321 4
987654321987654321 5
987654321987654321 7777
987654321987654321 10000
2 1
2 2
2 3
2 4
2 5
2 7777
2 10000
3 1
3 2
3 3
3 4
3 5
3 7777
3 10000
7777 1
7777 2
7777 3
7777 4
7777 5
7777 7777
7777 10000
987654321 1
987654321 2
987654321 3
987654321 4
987654321 5
987654321 7777
987654321 10000
9223372036854775806 1
9223372036854775806 2
9223372036854775806 3
9223372036854775806 4
9223372036854775806 5
9223372036854775806 7777
9223372036854775806 10000
0 0

Out:

Code: Select all

Case 1: 0 1 0
Case 2: 0 2 1
Case 3: 0 3 1
Case 4: 0 4 1
Case 5: 0 5 1
Case 6: 0 7777 1
Case 7: 0 10000 1
Case 8: 1 1 0
Case 9: 1 2 1
Case 10: 1 3 1
Case 11: 1 4 1
Case 12: 1 5 1
Case 13: 1 7777 1
Case 14: 1 10000 1
Case 15: 987654321987654321 1 0
Case 16: 987654321987654321 2 1
Case 17: 987654321987654321 3 1
Case 18: 987654321987654321 4 1
Case 19: 987654321987654321 5 1
Case 20: 987654321987654321 7777 4313
Case 21: 987654321987654321 10000 8221
Case 22: 2 1 0
Case 23: 2 2 1
Case 24: 2 3 0
Case 25: 2 4 3
Case 26: 2 5 3
Case 27: 2 7777 3
Case 28: 2 10000 3
Case 29: 3 1 0
Case 30: 3 2 1
Case 31: 3 3 2
Case 32: 3 4 1
Case 33: 3 5 0
Case 34: 3 7777 5
Case 35: 3 10000 5
Case 36: 7777 1 0
Case 37: 7777 2 1
Case 38: 7777 3 1
Case 39: 7777 4 1
Case 40: 7777 5 2
Case 41: 7777 7777 1240
Case 42: 7777 10000 3377
Case 43: 987654321 1 0
Case 44: 987654321 2 1
Case 45: 987654321 3 1
Case 46: 987654321 4 1
Case 47: 987654321 5 1
Case 48: 987654321 7777 4313
Case 49: 987654321 10000 8221
Case 50: 9223372036854775806 1 0
Case 51: 9223372036854775806 2 1
Case 52: 9223372036854775806 3 1
Case 53: 9223372036854775806 4 1
Case 54: 9223372036854775806 5 0
Case 55: 9223372036854775806 7777 5580
Case 56: 9223372036854775806 10000 2425

[yiuyuho]

I also ued the iterative method, and I tested it for b=1..10000 and they all comes back to (1,1).

However I am not sure if that's the case for ALL bases. My math is low, so if anyone knows about it please shine some light

[Spykaj]

I used 3x3 matrix:

Code: Select all

[3 1 1]   [1 1 0]^n
[1 1 1] * [1 0 0]
[0 0 0]   [1 0 1]

[setu basak]

i couldn't understand why i am running m upto the dd[m]and dd[m-1] are not equal to 1 and at last in case of printing dd[n%m]..can anyone explain it to me??

Code: Select all

#include <cstdio>
#include<iostream>
using namespace std;
long dd[1000000];
int main()
{
	long long n;
	long b, m;
	long cases = 0;
	while (1)
	{
		scanf("%lld %ld", &n, &b);
		if (!n && !b) break;
		cases++;
		dd[0] = 1;
		dd[1] = 1;
		for (m = 2; m<1000000; m++)
		{
			dd[m] = (dd[m - 1] + dd[m - 2] + 1) % b;
			if (dd[m] == 1 && dd[m - 1] == 1)
				break;
		}
		m--;
		
		printf("Case %ld: %lld %ld %ld\n", cases, n, b, dd[n%m]);
	}
	return 0;
}

[brianfry713]

Try the I/O in this thread.