10956 - Prime Suspect

[Emilio]

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!

[Solaris]

I am gettin WA in this problem.

Can someone post the o/p for the following samples ??

Thnx in advance.

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

And if someone has any tricky case .. plz provide the IO

[txandi]

Output from my AC program:

Code: Select all

There are 0 odd non-prime numbers between 3 and 3.
There are no failures in base 3.

There are 0 odd non-prime numbers between 89 and 89.
There are no failures in base 3.

There are 0 odd non-prime numbers between 89 and 89.
There are no failures in base 2.

There are 40408 odd non-prime 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 non-prime numbers between 100001 and 200000.
3 suspects fail in base 2:
104653
130561
196093

There are 41987 odd non-prime numbers between 200001 and 300000.
7 suspects fail in base 2:
220729
233017
252601
253241
256999
271951
280601

There are 42137 odd non-prime numbers between 300001 and 400000.
3 suspects fail in base 2:
314821
357761
390937

There are 42322 odd non-prime numbers between 400001 and 500000.
4 suspects fail in base 2:
458989
476971
486737
489997

There are 42440 odd non-prime numbers between 500001 and 600000.
2 suspects fail in base 2:
514447
580337

There are 42555 odd non-prime numbers between 600001 and 700000.
2 suspects fail in base 2:
635401
647089

There are 42592 odd non-prime numbers between 700001 and 800000.
1 suspects fail in base 2:
741751

There are 42677 odd non-prime numbers between 800001 and 900000.
5 suspects fail in base 2:
800605
818201
838861
873181
877099

There are 42776 odd non-prime numbers between 900001 and 1000000.
3 suspects fail in base 2:
916327
976873
983401

There are 40408 odd non-prime 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 non-prime numbers between 100001 and 200000.
7 suspects fail in base 3:
105163
111361
112141
148417
152551
182527
188191

There are 41987 odd non-prime numbers between 200001 and 300000.
8 suspects fail in base 3:
211411
218791
221761
226801
228073
282133
288163
293401

There are 42137 odd non-prime 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 non-prime numbers between 400001 and 500000.
5 suspects fail in base 3:
432821
443713
453259
478297
497503

There are 42440 odd non-prime numbers between 500001 and 600000.
4 suspects fail in base 3:
504913
512461
551881
563347

There are 42555 odd non-prime numbers between 600001 and 700000.
5 suspects fail in base 3:
625873
638731
655051
658711
679057

There are 42592 odd non-prime numbers between 700001 and 800000.
1 suspects fail in base 3:
709873

There are 42677 odd non-prime numbers between 800001 and 900000.
6 suspects fail in base 3:
801139
823213
859951
867043
876961
894781

There are 42776 odd non-prime numbers between 900001 and 1000000.
3 suspects fail in base 3:
951481
973241
994507

I can't think of any tricky input. Just be careful with overflows (I used unsigned long long int for the exponentiation).

Good Luck!

[Solaris]

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

[Cho]

Mu output:

Code: Select all

There are 1 odd non-prime numbers between 4294967295 and 0.
There are no failures in base 2.

There are 47 odd non-prime numbers between 4294967195 and 0.
There are no failures in base 2.

There are 465 odd non-prime numbers between 4294966295 and 0.
There are no failures in base 2.

There are 4554 odd non-prime numbers between 4294957295 and 0.
There are no failures in base 2.

There are 45546 odd non-prime numbers between 4294867295 and 0.
1 suspects fail in base 2:
4294901761

There are 1 odd non-prime numbers between 4294967295 and 0.
There are no failures in base 3.

There are 47 odd non-prime numbers between 4294967195 and 0.
There are no failures in base 3.

There are 465 odd non-prime numbers between 4294966295 and 0.
There are no failures in base 3.

There are 4554 odd non-prime numbers between 4294957295 and 0.
There are no failures in base 3.

There are 45546 odd non-prime numbers between 4294867295 and 0.
There are no failures in base 3.

[Solaris]

Hey Cho,

Why does your output shows the Max value as 0 ???

Min and Max will be between 3 and 4294967295 (inclusive)

[Cho]

Oops.. it should be:

Code: Select all

There are 1 odd non-prime numbers between 4294967295 and 4294967295.
There are no failures in base 2.

There are 47 odd non-prime numbers between 4294967195 and 4294967295.
There are no failures in base 2.

There are 465 odd non-prime numbers between 4294966295 and 4294967295.
There are no failures in base 2.

There are 4554 odd non-prime numbers between 4294957295 and 4294967295.
There are no failures in base 2.

There are 45546 odd non-prime numbers between 4294867295 and 4294967295.
1 suspects fail in base 2:
4294901761

There are 1 odd non-prime numbers between 4294967295 and 4294967295.
There are no failures in base 3.

There are 47 odd non-prime numbers between 4294967195 and 4294967295.
There are no failures in base 3.

There are 465 odd non-prime numbers between 4294966295 and 4294967295.
There are no failures in base 3.

There are 4554 odd non-prime numbers between 4294957295 and 4294967295.
There are no failures in base 3.

There are 45546 odd non-prime numbers between 4294867295 and 4294967295.
There are no failures in base 3.

The previous mistake is due to compiling my code with mingw while the code containing %llu.

[Solaris]

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

All values are stored as unsigned int (not int64).

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 ??

thnx to Cho and txandi again

[minskcity]

From the problem statement:

It can be proved that whenever the function Suspect(b, n) returns FALSE for some base b and an odd number n it is sure that n is not a prime number.

Isn't Suspect(7, 7) == false?

[Anindya]

I am getting TLE in this problem.I tried with segmented sieve & miller-rabin.In both cases I got tle.My segmented sieve is ok-I got ac on 10140
using this in .287 sec.I can't find my problem.Is there any special tricks. My code gives correct output for all the test cases given above.