tag:blogger.com,1999:blog-31057242994925183872024-02-06T21:38:54.735-08:00Numbers Far awayZabir Al Nazi Nabilhttp://www.blogger.com/profile/02906242193437991438noreply@blogger.comBlogger3125tag:blogger.com,1999:blog-3105724299492518387.post-61254576983581261262016-05-25T15:56:00.002-07:002016-05-25T15:59:20.955-07:00Codeforces 10 C<div dir="ltr" style="text-align: left;" trbidi="on">
When , I first attempted this problem (in a contest) I had no idea how to solve it.When, I saw the solution it seemed a lot easier but the solution requires some steps :-P<br />
<br />
<br />
<a href="http://codeforces.com/contest/10/problem/C">CF 10 C Digital Root</a><br />
<br />
The code with Documentation :-D<br />
<br />
<br />
<br />
//Lets first find all digital roots of i for i = 1 to N<br />
//There's a O(1) formula for digital root<br />
<br />
<br />
<br />
//We need to calculate all digital root up to max possible range as, when in the num_dr[dr*dr2]<br />
//We would need to calculate DR of dr*dr2 which maybe >N so,if we just run this loop<br />
up to N we 'll miss some values<br />
<br />
<br /> digital_root[x] = 1 + (x-1)%9 ; //https://en.wikipedia.org/wiki/Digital_root<br /> //for base b , 9 can be replaced with (b-1)<br />
<br />
//Now we need to find all such triplets (x,y,z) such that<br /> // z != x*y but digital_root(z) = digital_root(digital_root(x)*digital_root(y))<br /><br /> //Try to understand the statement carefully . It seemed a bit confusing to me first<br /><br /><br /> "Not long ago Billy came across such a problem, where there were given three natural numbers<br /> A, B and C from the range [1, N], and it was asked to check whether the equation AB = C<br /> is correct. Recently Billy studied the concept of a digital root of a number. We should<br /> remind you that a digital root d(x) of the number x is the sum s(x) of all the digits<br /> of this number, if s(x) ≤ 9, otherwise it is d(s(x)). For example, a digital root of<br /> the number 6543 is calculated as follows: d(6543) = d(6 + 5 + 4 + 3) = d(18) = 9.<br /> Billy has counted that the digital root of a product of numbers is equal to the<br /> digital root of the product of the factors' digital roots, i.e. d(xy) = d(d(x)d(y)).<br /> And the following solution to the problem came to his mind: to calculate the digital<br /> roots and check if this condition is met. However, Billy has doubts that this condition is sufficient."<br /> <br /><br /><br /><br />//So, in brief billy has invented an algorithm he believes that if<br />//for some triplets (A,B,C) it can be showed that DR(A) = DR(DR(B)*DR(C)) //DR for digital_root()<br />//Then , A = B*C<br />//For example ,<br />// DR(6) = DR(DR(3)*DR(2)) so, 6 = 3*2 -> Billy's algorithm gives correct result<br />// DR(21) = DR(DR(3)*DR(4)) but, 21 != 3*4 -> Billy's algorithm gives wrong result<br /><br />//You are asked to find the number of triplets (A,B,C) such that Billy's algorithm gives wrong answer<br /><br />//Observe , we can easily apply modular property and see that , from definition of digital root (That we used using %)<br />// If, A = B*C<br />//Then , A%9 = (B%9*C%9)%9<br />//But,that's the number of correct ans , we are looking for number of wrong answers<br />//So,lets calculate number of all ans for which , DR(A) = DR(DR(B)*DR(C)) both correct ans and wrong ans<br /><br />//This can be easily done<br />//Lets save number of digital_roots with value i ; i= 1 to 9<br />//As,we know digital root is bounded function [1 to 9]<br />//We use counters where we save this information<br /><br /><br />//Now a bit of combinatorics<br />//A simple example,<br />//You have "m" numbers whose digital root is x .You have "n" numbers whose digital root is y .<br />//and You have "o" numbers whose digital root is DR(x*y) . //and as we know DR(some number) is always >=1 .. <=9<br />//So, 1=< x <=9 1=< y <=9 1=< DR(x*y) <=9<br />//(x,y,DR(x*y)) is such a triplet<br />//How many triplets can be made this way<br />//for x we have m possibility ,for y we have n possibility ,for DR(x*y) we have o possibility<br /><br />
<br />//But now we must subtract all the correct ans<br />//How can we do that , easy by finding all such triplets<br />//A = B*C in the range 1 to N<br />//For example , if we fix N = 5<br />//such triplets are , (1,1,1) (2,1,2) (4,2,2) (3,1,3) (4,1,4) (5,1,5)<br />//We can show that , this can be calculated this way ,<br /><br /><br /> //1)number of X <=N which has factor 1 //2)number of X <=N which has factor 2 //3)number of X <=N which has factor 3 ...... //N)number of X <=N which has factor N<br /><br />//Why this works ? 1)-> (1,1,1) (2,1,2) (3,1,3) ..... (N,1,N)<br />//2)-> (2,1,2) (4,2,2) (6,2,3) ..... (N,2,N/2)<br />//..... This way we get all those triplets we are looking for<br />//And we number of X<=N with factor i is just floor(N/i)<br />//For example,1.. N has N numbers with factor 1 , 1.. N has N/2 numbers with factor 2 ...easy to realize<br /><br /><br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #f0f0f0; border-width: 0.1em 0.1em 0.1em 0.8em; border: solid gray; overflow: auto; padding: 0.2em 0.6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 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
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #60a0b0; font-style: italic;">/****************************************</span>
<span style="color: #60a0b0; font-style: italic;">@_@</span>
<span style="color: #60a0b0; font-style: italic;">Cat Got Bored *_*</span>
<span style="color: #60a0b0; font-style: italic;">#_#</span>
<span style="color: #60a0b0; font-style: italic;">*****************************************/</span>
<span style="color: #007020;">#include <bits/stdc++.h></span>
<span style="color: #007020;">#define loop(i,s,e) for(int i = s;i<=e;i++) </span><span style="color: #60a0b0; font-style: italic;">//including end point</span>
<span style="color: #007020;">#define pb(a) push_back(a)</span>
<span style="color: #007020;">#define sqr(x) ((x)*(x))</span>
<span style="color: #007020;">#define CIN ios_base::sync_with_stdio(0); cin.tie(0);</span>
<span style="color: #007020;">#define ll long long</span>
<span style="color: #007020;">#define ull unsigned long long</span>
<span style="color: #007020;">#define SZ(a) int(a.size())</span>
<span style="color: #007020;">#define read() freopen("input.txt", "r", stdin)</span>
<span style="color: #007020;">#define write() freopen("output.txt", "w", stdout)</span>
<span style="color: #007020;">#define ms(a,b) memset(a, b, sizeof(a))</span>
<span style="color: #007020;">#define all(v) v.begin(), v.end()</span>
<span style="color: #007020;">#define PI acos(-1.0)</span>
<span style="color: #007020;">#define pf printf</span>
<span style="color: #007020;">#define sfi(a) scanf("%d",&a);</span>
<span style="color: #007020;">#define sfii(a,b) scanf("%d %d",&a,&b);</span>
<span style="color: #007020;">#define sfl(a) scanf("%lld",&a);</span>
<span style="color: #007020;">#define sfll(a,b) scanf("%lld %lld",&a,&b);</span>
<span style="color: #007020;">#define mp make_pair</span>
<span style="color: #007020;">#define paii pair<int, int></span>
<span style="color: #007020;">#define padd pair<dd, dd></span>
<span style="color: #007020;">#define pall pair<ll, ll></span>
<span style="color: #007020;">#define fs first</span>
<span style="color: #007020;">#define sc second</span>
<span style="color: #007020;">#define CASE(t) printf("Case %d: ",++t) </span><span style="color: #60a0b0; font-style: italic;">// t initialized 0</span>
<span style="color: #007020;">#define INF 1000000000 </span><span style="color: #60a0b0; font-style: italic;">//10e9</span>
<span style="color: #007020;">#define EPS 1e-9</span>
<span style="color: #007020; font-weight: bold;">using</span> <span style="color: #007020; font-weight: bold;">namespace</span> std;
<span style="color: #902000;">int</span> digital_root[<span style="color: #40a070;">1000009</span>];
ll num_dr[<span style="color: #40a070;">10</span>];<span style="color: #60a0b0; font-style: italic;">//How many digital roots with value i</span>
<span style="color: #902000;">int</span> <span style="color: #06287e;">main</span>()
{
<span style="color: #902000;">int</span> N;
sfi(N);
ms(num_dr,<span style="color: #40a070;">0</span>);
<span style="color: #60a0b0; font-style: italic;">//Lets first find all digital roots of i for i = 1 to N</span>
<span style="color: #60a0b0; font-style: italic;">//There's a O(1) formula for digital root</span>
<span style="color: #902000;">int</span> N_max <span style="color: #666666;">=</span> <span style="color: #40a070;">1000005</span>;
loop(x,<span style="color: #40a070;">1</span>,N_max) <span style="color: #60a0b0; font-style: italic;">//We need to calculate all digital root up to max possible range as, when in the num_dr[dr*dr2]</span>
{ <span style="color: #60a0b0; font-style: italic;">//We would need to calculate DR of dr*dr2 which maybe >N so,if we just run this loop up to N we 'll miss some values</span>
digital_root[x] <span style="color: #666666;">=</span> <span style="color: #40a070;">1</span> <span style="color: #666666;">+</span> (x<span style="color: #666666;">-</span><span style="color: #40a070;">1</span>)<span style="color: #666666;">%</span><span style="color: #40a070;">9</span> ; <span style="color: #60a0b0; font-style: italic;">//https://en.wikipedia.org/wiki/Digital_root</span>
<span style="color: #60a0b0; font-style: italic;">//for base b , 9 can be replaced with (b-1)</span>
<span style="color: #007020; font-weight: bold;">if</span>(x<span style="color: #666666;"><=</span>N)
num_dr[ digital_root[x] ]<span style="color: #666666;">++</span>; <span style="color: #60a0b0; font-style: italic;">//We wont add to counter if x is bigger than N</span>
}
<span style="color: #60a0b0; font-style: italic;">//Now we need to find all such triplets (x,y,z) such that</span>
<span style="color: #60a0b0; font-style: italic;">// z != x*y but digital_root(z) = digital_root(digital_root(x)*digital_root(y))</span>
<span style="color: #60a0b0; font-style: italic;">//Try to understand the statement carefully . It seemed a bit confusing to me first</span>
<span style="color: #60a0b0; font-style: italic;">/* "Not long ago Billy came across such a problem, where there were given three natural numbers</span>
<span style="color: #60a0b0; font-style: italic;"> A, B and C from the range [1, N], and it was asked to check whether the equation AB = C</span>
<span style="color: #60a0b0; font-style: italic;"> is correct. Recently Billy studied the concept of a digital root of a number. We should</span>
<span style="color: #60a0b0; font-style: italic;"> remind you that a digital root d(x) of the number x is the sum s(x) of all the digits</span>
<span style="color: #60a0b0; font-style: italic;"> of this number, if s(x) ≤ 9, otherwise it is d(s(x)). For example, a digital root of</span>
<span style="color: #60a0b0; font-style: italic;"> the number 6543 is calculated as follows: d(6543) = d(6 + 5 + 4 + 3) = d(18) = 9.</span>
<span style="color: #60a0b0; font-style: italic;"> Billy has counted that the digital root of a product of numbers is equal to the</span>
<span style="color: #60a0b0; font-style: italic;"> digital root of the product of the factors' digital roots, i.e. d(xy) = d(d(x)d(y)).</span>
<span style="color: #60a0b0; font-style: italic;"> And the following solution to the problem came to his mind: to calculate the digital</span>
<span style="color: #60a0b0; font-style: italic;"> roots and check if this condition is met. However, Billy has doubts that this condition is sufficient."</span>
<span style="color: #60a0b0; font-style: italic;"> */</span>
<span style="color: #60a0b0; font-style: italic;">//So, in brief billy has invented an algorithm he believes that if</span>
<span style="color: #60a0b0; font-style: italic;">//for some triplets (A,B,C) it can be showed that DR(A) = DR(DR(B)*DR(C)) //DR for digital_root()</span>
<span style="color: #60a0b0; font-style: italic;">//Then , A = B*C</span>
<span style="color: #60a0b0; font-style: italic;">//For example ,</span>
<span style="color: #60a0b0; font-style: italic;">// DR(6) = DR(DR(3)*DR(2)) so, 6 = 3*2 -> Billy's algorithm gives correct result</span>
<span style="color: #60a0b0; font-style: italic;">// DR(21) = DR(DR(3)*DR(4)) but, 21 != 3*4 -> Billy's algorithm gives wrong result</span>
<span style="color: #60a0b0; font-style: italic;">//You are asked to find the number of triplets (A,B,C) such that Billy's algorithm gives wrong answer</span>
<span style="color: #60a0b0; font-style: italic;">//Observe , we can easily apply modular property and see that , from definition of digital root (That we used using %)</span>
<span style="color: #60a0b0; font-style: italic;">// If, A = B*C</span>
<span style="color: #60a0b0; font-style: italic;">//Then , A%9 = (B%9*C%9)%9</span>
<span style="color: #60a0b0; font-style: italic;">//But,that's the number of correct ans , we are looking for number of wrong answers</span>
<span style="color: #60a0b0; font-style: italic;">//So,lets calculate number of all ans for which , DR(A) = DR(DR(B)*DR(C)) both correct ans and wrong ans</span>
<span style="color: #60a0b0; font-style: italic;">//This can be easily done</span>
<span style="color: #60a0b0; font-style: italic;">//Lets save number of digital_roots with value i ; i= 1 to 9</span>
<span style="color: #60a0b0; font-style: italic;">//As,we know digital root is bounded function [1 to 9]</span>
<span style="color: #60a0b0; font-style: italic;">//We use counters where we save this information</span>
<span style="color: #60a0b0; font-style: italic;">//Now a bit of combinatorics</span>
<span style="color: #60a0b0; font-style: italic;">//A simple example,</span>
<span style="color: #60a0b0; font-style: italic;">//You have "m" numbers whose digital root is x .You have "n" numbers whose digital root is y .</span>
<span style="color: #60a0b0; font-style: italic;">//and You have "o" numbers whose digital root is DR(x*y) . //and as we know DR(some number) is always >=1 .. <=9</span>
<span style="color: #60a0b0; font-style: italic;">//So, 1=< x <=9 1=< y <=9 1=< DR(x*y) <=9</span>
<span style="color: #60a0b0; font-style: italic;">//(x,y,DR(x*y)) is such a triplet</span>
<span style="color: #60a0b0; font-style: italic;">//How many triplets can be made this way</span>
<span style="color: #60a0b0; font-style: italic;">//for x we have m possibility ,for y we have n possibility ,for DR(x*y) we have o possibility</span>
ll num_all_triplets <span style="color: #666666;">=</span> <span style="color: #40a070;">0</span>;
loop(dr,<span style="color: #40a070;">1</span>,<span style="color: #40a070;">9</span>) <span style="color: #60a0b0; font-style: italic;">//DR is in this range</span>
{
loop(dr2,<span style="color: #40a070;">1</span>,<span style="color: #40a070;">9</span>) <span style="color: #60a0b0; font-style: italic;">// We want to find such pairs x,y -> x*y this forms a valid triplet (x,y,xy)</span>
{
num_all_triplets<span style="color: #666666;">+=</span> num_dr[dr]<span style="color: #666666;">*</span>num_dr[dr2]<span style="color: #666666;">*</span>num_dr[ digital_root[dr<span style="color: #666666;">*</span>dr2] ];
}
}
<span style="color: #60a0b0; font-style: italic;">//But now we must subtract all the correct ans</span>
<span style="color: #60a0b0; font-style: italic;">//How can we do that , easy by finding all such triplets</span>
<span style="color: #60a0b0; font-style: italic;">//A = B*C in the range 1 to N</span>
<span style="color: #60a0b0; font-style: italic;">//For example , if we fix N = 5</span>
<span style="color: #60a0b0; font-style: italic;">//such triplets are , (1,1,1) (2,1,2) (4,2,2) (3,1,3) (4,1,4) (5,1,5)</span>
<span style="color: #60a0b0; font-style: italic;">//We can show that , this can be calculated this way ,</span>
<span style="color: #60a0b0; font-style: italic;">//1)number of X <=N which has factor 1 //2)number of X <=N which has factor 2 //3)number of X <=N which has factor 3 ...... //N)number of X <=N which has factor N</span>
<span style="color: #60a0b0; font-style: italic;">//Why this works ? 1)-> (1,1,1) (2,1,2) (3,1,3) ..... (N,1,N)</span>
<span style="color: #60a0b0; font-style: italic;">//2)-> (2,1,2) (4,2,2) (6,2,3) ..... (N,2,N/2)</span>
<span style="color: #60a0b0; font-style: italic;">//..... This way we get all those triplets we are looking for</span>
<span style="color: #60a0b0; font-style: italic;">//And we number of X<=N with factor i is just floor(N/i)</span>
<span style="color: #60a0b0; font-style: italic;">//For example,1.. N has N numbers with factor 1 , 1.. N has N/2 numbers with factor 2 ...easy to realize</span>
ll num_correct_triplets <span style="color: #666666;">=</span> <span style="color: #40a070;">0</span>;
loop(i,<span style="color: #40a070;">1</span>,N)
{
num_correct_triplets <span style="color: #666666;">+=</span> (N<span style="color: #666666;">/</span>i) ; <span style="color: #60a0b0; font-style: italic;">//Works same way as floor function</span>
}
ll final_ans <span style="color: #666666;">=</span> num_all_triplets <span style="color: #666666;">-</span> num_correct_triplets;
cout<span style="color: #666666;"><<</span>final_ans<span style="color: #666666;"><<</span>endl;
<span style="color: #007020; font-weight: bold;">return</span> <span style="color: #40a070;">0</span>;
}
</pre>
</td></tr>
</tbody></table>
</div>
</div>
Zabir Al Nazi Nabilhttp://www.blogger.com/profile/02906242193437991438noreply@blogger.com0tag:blogger.com,1999:blog-3105724299492518387.post-68866897100369159432015-12-12T02:55:00.001-08:002015-12-12T02:55:25.636-08:00A mod B in O(number_of_digit_in(A))<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
<div dir="ltr" style="text-align: left;" trbidi="on">
Lets say you have a Big Integer A and an integer B . You want to calculate A mod B in O(length_of_(A)) time complexity . How to do that?<br />
<br />
Lets say : A = 1234 (Not that big :-P ) and B = 6<br />
<br />
I want to calculate 1234 % 6 . Now ,<br />
<br />
s1 = 1234 % 6 = ((123%6)*10 + 4)%6<br />
= (s2*10 + 4) %6 [If I know s2 I can calculate 1234 % 6 in O(1) now]<br />
<br />
s2 = (123%6) = ((12%6)*10 + 3)%6<br />
= (s3*10 + 3)%6 [If I know s3 I can calculate 1234 % 6 in O(1) now]<br />
<br />
s3 = (12 % 6 ) = ( (1%6)*10 + 2)%6<br />
= ( s4*10 + 2) % 6 [If I know s4 I can calculate 1234 % 6 in O(1) and s4 can be calculated in O(1)]<br />
<br />
<br />
Now, We can easily implement this with a single loop which runs in O(n) . where,length(A) = n<br />
<br />
So,<br />
<br />
<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #f0f3f3; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #0099ff; font-style: italic;">//A is taken as string</span>
<span style="color: #0099ff; font-style: italic;">//mod = B</span>
<span style="color: #007788; font-weight: bold;">int</span> AmodB <span style="color: #555555;">=</span> <span style="color: #ff6600;">0</span>;
<span style="color: #006699; font-weight: bold;">for</span>(<span style="color: #007788; font-weight: bold;">int</span> a<span style="color: #555555;">=</span><span style="color: #ff6600;">0</span>;a<span style="color: #555555;"><</span>s.length();a<span style="color: #555555;">++</span>)
{
AmodB <span style="color: #555555;">=</span> (AmodB<span style="color: #555555;">*</span><span style="color: #ff6600;">10</span> <span style="color: #555555;">+</span> (<span style="color: #007788; font-weight: bold;">int</span>)(s[a] <span style="color: #555555;">-</span> <span style="color: #cc3300;">'0'</span>))<span style="color: #555555;">%</span>mod;
} </pre>
</td></tr>
</tbody></table>
</div>
</div>
<br />
AmodB is initially (0*10 + 1)%6 = 1 (s4)<br />
then, (1*10 + 2)%6 = 0 (s3)<br />
then, (0*10 + 3)%6 = 3 (s2)<br />
and finally, (3*10 + 4)%6 = 4 (s1)<br />
<br />
Theory : <span class="comment-copy">For any X , (X*k + m)%d = ((k%d)*X + m)%d</span><br />
<br />
<span class="comment-copy">as, k can be written as a (multiple of d + remainder) this way k = a*d + k%d ,for some integer a.</span><br />
<span class="comment-copy">now, (X*k + m)%d</span><br />
<span class="comment-copy"><br /></span>
<span class="comment-copy"> = (X*(a*d + k%d) + m)%d</span><br />
<span class="comment-copy"> = (X*a*d + X*k%d + m)%d</span><br />
<span class="comment-copy"> = (k%d*X + m)%d [as,X*a*d % d = 0]</span><br />
<span class="comment-copy"><br /></span>
<span class="comment-copy">Now,put X = 10</span><br />
<span class="comment-copy"><br /></span>
<span class="comment-copy"><br /></span>
<span class="comment-copy"><br /></span>
<span class="comment-copy">Another approach : (1234)%6 = (4 + 3*10 + 2*100 + 1*1000)%6</span><br />
<span class="comment-copy"><br /></span>
<span class="comment-copy"><br /></span>
<span class="comment-copy">so, ans = (sigma(i = 0 to n-1) (10^i*digit[i])%mod</span><br />
<span class="comment-copy">The problem is how can I calculate (10^i%mod) efficiently and avoiding overflow?</span><br />
<span class="comment-copy"><br /></span>
<span class="comment-copy">Look, 10^5%mod = ((10^4)%mod*(10%mod))%mod</span><br />
<span class="comment-copy">So,we can just save 10^(i-1)%mod in the loop and in the i'th iteration I'll find 10^i%mod by multiplying 10^(i-1)%mod [which I have already saved] and 10%mod [I can also save this into a variable to avoid repeated calculation] and "mod"ing the multiplied result.</span><br />
<span class="comment-copy"><br /></span>
<span class="comment-copy"><br /></span></div>
<!-- HTML generated using hilite.me --><br />
<div style="background: #ffffff; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #333399; font-weight: bold;">int</span> mod_loop <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">1</span>;
<span style="color: #333399; font-weight: bold;">int</span> tmp <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">0</span>;
<span style="color: #333399; font-weight: bold;">int</span> ten_mod <span style="color: #333333;">=</span> <span style="color: #0000dd; font-weight: bold;">10</span><span style="color: #333333;">%</span>mod; <span style="color: #888888;">//saving this</span>
<span style="color: #008800; font-weight: bold;">for</span>(<span style="color: #333399; font-weight: bold;">int</span> a<span style="color: #333333;">=</span>s.length()<span style="color: #333333;">-</span><span style="color: #0000dd; font-weight: bold;">1</span>;a<span style="color: #333333;">>=</span><span style="color: #0000dd; font-weight: bold;">0</span>;a<span style="color: #333333;">--</span>)
{
tmp<span style="color: #333333;">+=</span>(mod_loop<span style="color: #333333;">*</span>(<span style="color: #333399; font-weight: bold;">int</span>)(s[a] <span style="color: #333333;">-</span> <span style="color: #0044dd;">'0'</span> ) )<span style="color: #333333;">%</span>mod;
mod_loop <span style="color: #333333;">=</span>((mod_loop)<span style="color: #333333;">*</span>ten_mod)<span style="color: #333333;">%</span>mod;
}
<span style="color: #333399; font-weight: bold;">int</span> ans <span style="color: #333333;">=</span> tmp<span style="color: #333333;">%</span>mod
</pre>
</td></tr>
</tbody></table>
</div>
<br />
<br />
<br />
Problems : Type 1) You'd need to mod a Big Integer very fast / You'd need to check divisibility (if B divides A) avoiding overflow and in O(length(A))<br />
<br />
Type 2) You'll be given B and you have to find A such that B divides A and digits of A has a certain pattern such as A = 1111111........ , 12121212121212.................<br />
<br /></div>
Zabir Al Nazi Nabilhttp://www.blogger.com/profile/02906242193437991438noreply@blogger.com0tag:blogger.com,1999:blog-3105724299492518387.post-56931953974087276312015-12-09T06:26:00.002-08:002015-12-09T06:26:29.238-08:00LOJ 1010 Knights<div dir="ltr" style="text-align: left;" trbidi="on">
Problem id : <a href="http://lightoj.com/volume_showproblem.php?problem=1010">LOJ 1010</a><br />
<br />
<br />
To maximize the number of knights we have to place knights in a particular pattern.<br />
<div class="separator" style="clear: both; text-align: center;">
<a href="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhNOMa68F_zWrsglrwRCEu6nPr8E-N5HCQ4H6FX7qXI9YOlD-sSTme74WgdvHNGRZ7aPWjkJrCZiiEeueohbwNc3GoC8dnczfzPTLS_SwsqKcQvDUdXr22G_YSSbbHaUUIgRCyYOY6ykgWu/s1600/horse.png" imageanchor="1" style="margin-left: 1em; margin-right: 1em;"><img border="0" height="202" src="https://blogger.googleusercontent.com/img/b/R29vZ2xl/AVvXsEhNOMa68F_zWrsglrwRCEu6nPr8E-N5HCQ4H6FX7qXI9YOlD-sSTme74WgdvHNGRZ7aPWjkJrCZiiEeueohbwNc3GoC8dnczfzPTLS_SwsqKcQvDUdXr22G_YSSbbHaUUIgRCyYOY6ykgWu/s320/horse.png" width="320" /></a></div>
<br />
<br />
Code :<br />
<br />
<br />
<!-- HTML generated using hilite.me --><br />
<div style="background: #f0f3f3; border-width: .1em .1em .1em .8em; border: solid gray; overflow: auto; padding: .2em .6em; width: auto;">
<table><tbody>
<tr><td><pre style="line-height: 125%; margin: 0;"> 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</pre>
</td><td><pre style="line-height: 125%; margin: 0;"><span style="color: #009999;">#include<stdio.h></span>
<span style="color: #007788; font-weight: bold;">int</span> <span style="color: #cc00ff;">main</span>()
{
<span style="color: #007788; font-weight: bold;">int</span> tc,cas <span style="color: #555555;">=</span> <span style="color: #ff6600;">0</span> ;
<span style="color: #007788; font-weight: bold;">int</span> ans <span style="color: #555555;">=</span> <span style="color: #ff6600;">0</span>;
scanf(<span style="color: #cc3300;">"%d"</span>,<span style="color: #555555;">&</span>tc);
<span style="color: #006699; font-weight: bold;">while</span>(tc<span style="color: #555555;">--</span>)
{
<span style="color: #007788; font-weight: bold;">int</span> m,n;
scanf(<span style="color: #cc3300;">"%d %d"</span>,<span style="color: #555555;">&</span>m,<span style="color: #555555;">&</span>n);
<span style="color: #0099ff; font-style: italic;">//ans = solve(m,n);</span>
<span style="color: #0099ff; font-style: italic;">//ROW / COL = 1</span>
<span style="color: #006699; font-weight: bold;">if</span>(m<span style="color: #555555;">==</span><span style="color: #ff6600;">1</span>)
ans <span style="color: #555555;">=</span> n;
<span style="color: #006699; font-weight: bold;">else</span> <span style="color: #006699; font-weight: bold;">if</span>(n<span style="color: #555555;">==</span><span style="color: #ff6600;">1</span>)
ans <span style="color: #555555;">=</span> m;
<span style="color: #0099ff; font-style: italic;">//ROW / COL = 2</span>
<span style="color: #006699; font-weight: bold;">else</span> <span style="color: #006699; font-weight: bold;">if</span>(m<span style="color: #555555;">==</span><span style="color: #ff6600;">2</span>)
{
ans <span style="color: #555555;">=</span> <span style="color: #ff6600;">0</span>;
<span style="color: #006699; font-weight: bold;">for</span>(<span style="color: #007788; font-weight: bold;">int</span> i<span style="color: #555555;">=</span><span style="color: #ff6600;">1</span>,cn<span style="color: #555555;">=</span><span style="color: #ff6600;">1</span>; i<span style="color: #555555;"><=</span>n; i<span style="color: #555555;">+=</span><span style="color: #ff6600;">4</span>,cn<span style="color: #555555;">++</span>)
{
<span style="color: #0099ff; font-style: italic;">// if(cn&1)</span>
{
<span style="color: #006699; font-weight: bold;">if</span>(i<span style="color: #555555;">==</span>n)
ans <span style="color: #555555;">+=</span><span style="color: #ff6600;">2</span>;
<span style="color: #006699; font-weight: bold;">else</span>
ans <span style="color: #555555;">+=</span> <span style="color: #ff6600;">4</span>;
}
}
}
<span style="color: #006699; font-weight: bold;">else</span> <span style="color: #006699; font-weight: bold;">if</span>(n<span style="color: #555555;">==</span><span style="color: #ff6600;">2</span>)
{
ans <span style="color: #555555;">=</span> <span style="color: #ff6600;">0</span>;
<span style="color: #006699; font-weight: bold;">for</span>(<span style="color: #007788; font-weight: bold;">int</span> i<span style="color: #555555;">=</span><span style="color: #ff6600;">1</span>,cn<span style="color: #555555;">=</span><span style="color: #ff6600;">1</span>; i<span style="color: #555555;"><=</span>m; i<span style="color: #555555;">+=</span><span style="color: #ff6600;">4</span>,cn<span style="color: #555555;">++</span>)
{
<span style="color: #0099ff; font-style: italic;">// if(cn&1)</span>
{
<span style="color: #006699; font-weight: bold;">if</span>(i<span style="color: #555555;">==</span>m)
ans <span style="color: #555555;">+=</span><span style="color: #ff6600;">2</span>;
<span style="color: #006699; font-weight: bold;">else</span>
ans <span style="color: #555555;">+=</span> <span style="color: #ff6600;">4</span>;
}
}
}
<span style="color: #0099ff; font-style: italic;">//ROW / COL > 2</span>
<span style="color: #006699; font-weight: bold;">else</span> <span style="color: #006699; font-weight: bold;">if</span>(m<span style="color: #555555;">&</span><span style="color: #ff6600;">1</span>)<span style="color: #0099ff; font-style: italic;">//odd</span>
{
<span style="color: #006699; font-weight: bold;">if</span>(n<span style="color: #555555;">&</span><span style="color: #ff6600;">1</span>)<span style="color: #0099ff; font-style: italic;">//odd</span>
ans<span style="color: #555555;">=</span> (m<span style="color: #555555;">/</span><span style="color: #ff6600;">2</span> <span style="color: #555555;">+</span> <span style="color: #ff6600;">1</span>)<span style="color: #555555;">*</span>(n<span style="color: #555555;">/</span><span style="color: #ff6600;">2</span> <span style="color: #555555;">+</span> <span style="color: #ff6600;">1</span>) <span style="color: #555555;">+</span> (m<span style="color: #555555;">/</span><span style="color: #ff6600;">2</span>)<span style="color: #555555;">*</span>(n<span style="color: #555555;">/</span><span style="color: #ff6600;">2</span>);
<span style="color: #006699; font-weight: bold;">else</span> <span style="color: #0099ff; font-style: italic;">//m odd n even</span>
ans<span style="color: #555555;">=</span> (m<span style="color: #555555;">/</span><span style="color: #ff6600;">2</span> <span style="color: #555555;">+</span> <span style="color: #ff6600;">1</span>)<span style="color: #555555;">*</span>(n<span style="color: #555555;">/</span><span style="color: #ff6600;">2</span>) <span style="color: #555555;">+</span> (m<span style="color: #555555;">/</span><span style="color: #ff6600;">2</span>)<span style="color: #555555;">*</span>(n<span style="color: #555555;">/</span><span style="color: #ff6600;">2</span>);
}
<span style="color: #006699; font-weight: bold;">else</span>
{
<span style="color: #006699; font-weight: bold;">if</span>(n<span style="color: #555555;">&</span><span style="color: #ff6600;">1</span>)<span style="color: #0099ff; font-style: italic;">//odd</span>
ans<span style="color: #555555;">=</span> (m<span style="color: #555555;">/</span><span style="color: #ff6600;">2</span>)<span style="color: #555555;">*</span>(n<span style="color: #555555;">/</span><span style="color: #ff6600;">2</span> <span style="color: #555555;">+</span> <span style="color: #ff6600;">1</span>) <span style="color: #555555;">+</span> (m<span style="color: #555555;">/</span><span style="color: #ff6600;">2</span>)<span style="color: #555555;">*</span>(n<span style="color: #555555;">/</span><span style="color: #ff6600;">2</span>);
<span style="color: #006699; font-weight: bold;">else</span>
ans<span style="color: #555555;">=</span> (m<span style="color: #555555;">/</span><span style="color: #ff6600;">2</span>)<span style="color: #555555;">*</span>(n<span style="color: #555555;">/</span><span style="color: #ff6600;">2</span>) <span style="color: #555555;">+</span> (m<span style="color: #555555;">/</span><span style="color: #ff6600;">2</span>)<span style="color: #555555;">*</span>(n<span style="color: #555555;">/</span><span style="color: #ff6600;">2</span>);
}
printf(<span style="color: #cc3300;">"Case %d: %d</span><span style="color: #cc3300; font-weight: bold;">\n</span><span style="color: #cc3300;">"</span>,<span style="color: #555555;">++</span>cas,ans);
}
<span style="color: #006699; font-weight: bold;">return</span> <span style="color: #ff6600;">0</span>;
}
</pre>
</td></tr>
</tbody></table>
</div>
</div>
Zabir Al Nazi Nabilhttp://www.blogger.com/profile/02906242193437991438noreply@blogger.com0