10956  Prime Suspect
Moderator: Board moderators
Hello all!
I want to put my point of view about the time limit.
I agree with the four seconds of time limit because with a bigger limit you can use the method of the three bases for solve the problem, and with this, the problem would be a very straighforward problem. I prefer for this problem that you must use another more elaborate method.
Well, maybe only one second more!
Only that!
I want to put my point of view about the time limit.
I agree with the four seconds of time limit because with a bigger limit you can use the method of the three bases for solve the problem, and with this, the problem would be a very straighforward problem. I prefer for this problem that you must use another more elaborate method.
Well, maybe only one second more!
Only that!

 Learning poster
 Posts: 99
 Joined: Sun Apr 06, 2003 5:53 am
 Location: Dhaka, Bangladesh
 Contact:
I am gettin WA in this problem.
Can someone post the o/p for the following samples ??
Thnx in advance.
Can someone post the o/p for the following samples ??
Thnx in advance.
And if someone has any tricky case .. plz provide the IO
3 3 3
3 89 89
2 89 89
2 3 100000
2 100001 200000
2 200001 300000
2 300001 400000
2 400001 500000
2 500001 600000
2 600001 700000
2 700001 800000
2 800001 900000
2 900001 1000000
3 3 100000
3 100001 200000
3 200001 300000
3 300001 400000
3 400001 500000
3 500001 600000
3 600001 700000
3 700001 800000
3 800001 900000
3 900001 1000000
2 4294967295 4294967295
2 4294967195 4294967295
2 4294966295 4294967295
2 4294957295 4294967295
2 4294867295 4294967295
3 4294967295 4294967295
3 4294967195 4294967295
3 4294966295 4294967295
3 4294957295 4294967295
3 4294867295 4294967295
Where's the "Any" key?
Output from my AC program:
I can't think of any tricky input. Just be careful with overflows (I used unsigned long long int for the exponentiation).
Good Luck!
Code: Select all
There are 0 odd nonprime numbers between 3 and 3.
There are no failures in base 3.
There are 0 odd nonprime numbers between 89 and 89.
There are no failures in base 3.
There are 0 odd nonprime numbers between 89 and 89.
There are no failures in base 2.
There are 40408 odd nonprime numbers between 3 and 100000.
16 suspects fail in base 2:
2047
3277
4033
4681
8321
15841
29341
42799
49141
52633
65281
74665
80581
85489
88357
90751
There are 41608 odd nonprime numbers between 100001 and 200000.
3 suspects fail in base 2:
104653
130561
196093
There are 41987 odd nonprime numbers between 200001 and 300000.
7 suspects fail in base 2:
220729
233017
252601
253241
256999
271951
280601
There are 42137 odd nonprime numbers between 300001 and 400000.
3 suspects fail in base 2:
314821
357761
390937
There are 42322 odd nonprime numbers between 400001 and 500000.
4 suspects fail in base 2:
458989
476971
486737
489997
There are 42440 odd nonprime numbers between 500001 and 600000.
2 suspects fail in base 2:
514447
580337
There are 42555 odd nonprime numbers between 600001 and 700000.
2 suspects fail in base 2:
635401
647089
There are 42592 odd nonprime numbers between 700001 and 800000.
1 suspects fail in base 2:
741751
There are 42677 odd nonprime numbers between 800001 and 900000.
5 suspects fail in base 2:
800605
818201
838861
873181
877099
There are 42776 odd nonprime numbers between 900001 and 1000000.
3 suspects fail in base 2:
916327
976873
983401
There are 40408 odd nonprime numbers between 3 and 100000.
23 suspects fail in base 3:
121
703
1891
3281
8401
8911
10585
12403
16531
18721
19345
23521
31621
44287
47197
55969
63139
74593
79003
82513
87913
88573
97567
There are 41608 odd nonprime numbers between 100001 and 200000.
7 suspects fail in base 3:
105163
111361
112141
148417
152551
182527
188191
There are 41987 odd nonprime numbers between 200001 and 300000.
8 suspects fail in base 3:
211411
218791
221761
226801
228073
282133
288163
293401
There are 42137 odd nonprime numbers between 300001 and 400000.
11 suspects fail in base 3:
313447
320167
327781
328021
340033
359341
364231
365713
385003
385201
399001
There are 42322 odd nonprime numbers between 400001 and 500000.
5 suspects fail in base 3:
432821
443713
453259
478297
497503
There are 42440 odd nonprime numbers between 500001 and 600000.
4 suspects fail in base 3:
504913
512461
551881
563347
There are 42555 odd nonprime numbers between 600001 and 700000.
5 suspects fail in base 3:
625873
638731
655051
658711
679057
There are 42592 odd nonprime numbers between 700001 and 800000.
1 suspects fail in base 3:
709873
There are 42677 odd nonprime numbers between 800001 and 900000.
6 suspects fail in base 3:
801139
823213
859951
867043
876961
894781
There are 42776 odd nonprime numbers between 900001 and 1000000.
3 suspects fail in base 3:
951481
973241
994507
Good Luck!

 Learning poster
 Posts: 99
 Joined: Sun Apr 06, 2003 5:53 am
 Location: Dhaka, Bangladesh
 Contact:
Dear txandi, thnx for your prompt reply.
Your o/p matches with mine Can u give me output for the rest of my samples ??
2 4294967295 4294967295
2 4294967195 4294967295
2 4294966295 4294967295
2 4294957295 4294967295
2 4294867295 4294967295
3 4294967295 4294967295
3 4294967195 4294967295
3 4294966295 4294967295
3 4294957295 4294967295
3 4294867295 4294967295
0 0 0
Your o/p matches with mine Can u give me output for the rest of my samples ??
2 4294967295 4294967295
2 4294967195 4294967295
2 4294966295 4294967295
2 4294957295 4294967295
2 4294867295 4294967295
3 4294967295 4294967295
3 4294967195 4294967295
3 4294966295 4294967295
3 4294957295 4294967295
3 4294867295 4294967295
0 0 0
Where's the "Any" key?
Mu output:
Code: Select all
There are 1 odd nonprime numbers between 4294967295 and 0.
There are no failures in base 2.
There are 47 odd nonprime numbers between 4294967195 and 0.
There are no failures in base 2.
There are 465 odd nonprime numbers between 4294966295 and 0.
There are no failures in base 2.
There are 4554 odd nonprime numbers between 4294957295 and 0.
There are no failures in base 2.
There are 45546 odd nonprime numbers between 4294867295 and 0.
1 suspects fail in base 2:
4294901761
There are 1 odd nonprime numbers between 4294967295 and 0.
There are no failures in base 3.
There are 47 odd nonprime numbers between 4294967195 and 0.
There are no failures in base 3.
There are 465 odd nonprime numbers between 4294966295 and 0.
There are no failures in base 3.
There are 4554 odd nonprime numbers between 4294957295 and 0.
There are no failures in base 3.
There are 45546 odd nonprime numbers between 4294867295 and 0.
There are no failures in base 3.
Oops.. it should be:
The previous mistake is due to compiling my code with mingw while the code containing %llu.
Code: Select all
There are 1 odd nonprime numbers between 4294967295 and 4294967295.
There are no failures in base 2.
There are 47 odd nonprime numbers between 4294967195 and 4294967295.
There are no failures in base 2.
There are 465 odd nonprime numbers between 4294966295 and 4294967295.
There are no failures in base 2.
There are 4554 odd nonprime numbers between 4294957295 and 4294967295.
There are no failures in base 2.
There are 45546 odd nonprime numbers between 4294867295 and 4294967295.
1 suspects fail in base 2:
4294901761
There are 1 odd nonprime numbers between 4294967295 and 4294967295.
There are no failures in base 3.
There are 47 odd nonprime numbers between 4294967195 and 4294967295.
There are no failures in base 3.
There are 465 odd nonprime numbers between 4294966295 and 4294967295.
There are no failures in base 3.
There are 4554 odd nonprime numbers between 4294957295 and 4294967295.
There are no failures in base 3.
There are 45546 odd nonprime numbers between 4294867295 and 4294967295.
There are no failures in base 3.

 Learning poster
 Posts: 99
 Joined: Sun Apr 06, 2003 5:53 am
 Location: Dhaka, Bangladesh
 Contact:
thnx Cho and txandi, I have got AC at last. It was one of those overflow errors. Not only in the Moduler Exponentiation part but also while storing Xi values I had to use Unsigned Long Long
thnx to Cho and txandi again
I know the ultimate result of each operation will fit into unsigned but dont you have to use UNSIGNED LONG LONG for the intermediate results ??? Or is there any other method of Mod. Exp. that I dont know about ??Renat wrote:All values are stored as unsigned int (not int64).
thnx to Cho and txandi again
Where's the "Any" key?