LightOJ-Solutions/1090-Trailing-Zeroes-II.cpp at master · hackerkid/LightOJ-Solutions · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <iostream>
#include <stdio.h>
using namespace std;

#define sz 1000000

long long dp2[sz + 5];
long long dp5[sz + 5];

int main()
{
	int j;
	int x;
	int n;
	int r;
	int p;
	int q;
	int t;
	long long a;
	long long b;
	long long temp;
	long long two;
	long long five;

	dp2[1] = 0;
	dp5[1] = 0;
	for (int i = 2; i <= sz; i++) {
		j = i;

		temp = 0;

		while(j % 2 == 0) {
			temp++;
			j = j / 2;
		}

		dp2[i] = dp2[i-1] + temp;

		j = i;

		temp = 0;

		while(j % 5 == 0) {
			temp++;
			j = j / 5;
		}

		dp5[i] = dp5[i-1] + temp;

	}

	scanf("%d", &t);

	for (int cs = 1; cs <= t; cs++) {
		scanf("%d", &n);
		scanf("%d", &r);
		scanf("%d", &p);
		scanf("%d", &q);

		two = (dp2[p] - dp2[p-1]) * q;
		five = (dp5[p] - dp5[p-1]) * q;

		two += (dp2[n] - dp2[n-r]);
		five += (dp5[n] - dp5[n-r]);

		two = two - dp2[r];
		five = five - dp5[r];

		a = min(two, five);

		printf("Case %d: %lld\n", cs, a);
	}


}