ENG  RUS Timus Online Judge
Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 2102. Michael and Cryptography

WA#54
Posted by Delta67 18 Apr 2017 08:13
What's the test like?
Re: WA#54
Posted by Mahilewets 18 Apr 2017 10:59
Very stupid algo that in a single loop from i=2 to 2*10^6 checks whether i|N works
Because of if we take any combination Factor[20] of primes where at least one Factor[j]>2*10^6 than product of Factor[j] larger than 10^18.
Re: WA#54
Posted by Marginean Ciprian 3 May 2017 03:26
Try tests like 2^18 multiplied with twin primes, all should yield yes.
Test cases:
3932160
3145728
7864320
34603008
80216064
228065280
451411968
927989760
1340080128
2700607488
3029336064
4956094464
5858918400
8446279680
9613344768
10225188864
13567524864
15036579840
19039518720
20772814848
25436356608
31655460864
46132101120
48809115648
55831953408
71293206528
85021163520
94214553600
99957080064
107878023168
114016911360
171780341760
176911024128
179504676864
192756056064
203696898048
All yes.
Re: WA#54
Posted by Marginean Ciprian 4 May 2017 16:58
The thing is you should go up to sqrt(n/(2^18)) not sqrt(n/(2^19)).
Re: WA#54
Posted by Lucian Ilea 27 Jul 2017 12:36
Dear Ciprian, I think that some of your samples are wrong. 3145728=2^20*3^1 and the answer should be No. The same situation is for the last number, 203696898048 (my accepted program outputs No).
Re: WA#54
Posted by Rodrigo Morales [UTEC] 18 Oct 2017 03:29
Marginean Ciprian, I think you are wrong, I got this.

Number: 3932160 -> Yes
Number: 3145728 -> No
Number: 7864320 -> No
Number: 34603008 -> No
Number: 80216064 -> No
Number: 228065280 -> No
Number: 451411968 -> No
Number: 927989760 -> No
Number: 1340080128 -> No
Number: 2700607488 -> No
Number: 3029336064 -> No
Number: 4956094464 -> No
Number: 5858918400 -> No
Number: 8446279680 -> No
Number: 9613344768 -> No
Number: 10225188864 -> No
Number: 13567524864 -> No
Number: 15036579840 -> No
Number: 19039518720 -> No
Number: 20772814848 -> No
Number: 25436356608 -> No
Number: 31655460864 -> No
Number: 46132101120 -> No
Number: 48809115648 -> No
Number: 55831953408 -> No
Number: 71293206528 -> No
Number: 85021163520 -> No
Number: 94214553600 -> No
Number: 99957080064 -> No
Number: 107878023168 -> No
Number: 114016911360 -> No
Number: 171780341760 -> No
Number: 176911024128 -> No
Number: 179504676864 -> No
Number: 192756056064 -> No
Number: 203696898048 -> No
Re: WA#54
Posted by Rodrigo Morales [UTEC] 18 Oct 2017 03:33
Proof:

3932160
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 5
Repetitions: 18 1 1
Sum of repetitions equals 20?: Yes

3145728
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3
Repetitions: 20 1
Sum of repetitions equals 20?: No

7864320
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 5
Repetitions: 19 1 1
Sum of repetitions equals 20?: No

34603008
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 11
Repetitions: 20 1 1
Sum of repetitions equals 20?: No

80216064
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 17
Repetitions: 19 2 1
Sum of repetitions equals 20?: No

228065280
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 5 29
Repetitions: 19 1 1 1
Sum of repetitions equals 20?: No

451411968
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 7 41
Repetitions: 19 1 1 1
Sum of repetitions equals 20?: No

927989760
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 5 59
Repetitions: 20 1 1 1
Sum of repetitions equals 20?: No

1340080128
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 71
Repetitions: 21 2 1
Sum of repetitions equals 20?: No

2700607488
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 17 101
Repetitions: 19 1 1 1
Sum of repetitions equals 20?: No

3029336064
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 107
Repetitions: 20 3 1
Sum of repetitions equals 20?: No

4956094464
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 23 137
Repetitions: 19 1 1 1
Sum of repetitions equals 20?: No

5858918400
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 5 5 149
Repetitions: 19 1 2 1
Sum of repetitions equals 20?: No

8446279680
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 5 179
Repetitions: 20 2 1 1
Sum of repetitions equals 20?: No

9613344768
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 191
Repetitions: 24 1 1
Sum of repetitions equals 20?: No

10225188864
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 11 197
Repetitions: 19 2 1 1
Sum of repetitions equals 20?: No

13567524864
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 19 227
Repetitions: 20 1 1 1
Sum of repetitions equals 20?: No

15036579840
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 5 239
Repetitions: 22 1 1 1
Sum of repetitions equals 20?: No

19039518720
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 5 269
Repetitions: 19 3 1 1
Sum of repetitions equals 20?: No

20772814848
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 47 281
Repetitions: 19 1 1 1
Sum of repetitions equals 20?: No

25436356608
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 13 311
Repetitions: 21 1 1 1
Sum of repetitions equals 20?: No

31655460864
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 29 347
Repetitions: 20 1 1 1
Sum of repetitions equals 20?: No

46132101120
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 5 7 419
Repetitions: 20 1 1 1 1
Sum of repetitions equals 20?: No

48809115648
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 431
Repetitions: 22 3 1
Sum of repetitions equals 20?: No

55831953408
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 7 11 461
Repetitions: 19 1 1 1 1
Sum of repetitions equals 20?: No

71293206528
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 29 521
Repetitions: 19 2 1 1
Sum of repetitions equals 20?: No

85021163520
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 5 19 569
Repetitions: 19 1 1 1 1
Sum of repetitions equals 20?: No

94214553600
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 5 5 599
Repetitions: 21 1 2 1
Sum of repetitions equals 20?: No

99957080064
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 103 617
Repetitions: 19 1 1 1
Sum of repetitions equals 20?: No

107878023168
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 107 641
Repetitions: 19 1 1 1
Sum of repetitions equals 20?: No

114016911360
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 5 11 659
Repetitions: 20 1 1 1 1
Sum of repetitions equals 20?: No

171780341760
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 5 809
Repetitions: 19 4 1 1
Sum of repetitions equals 20?: No

176911024128
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 137 821
Repetitions: 19 1 1 1
Sum of repetitions equals 20?: No

179504676864
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 23 827
Repetitions: 20 2 1 1
Sum of repetitions equals 20?: No

192756056064
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 11 13 857
Repetitions: 19 1 1 1 1
Sum of repetitions equals 20?: No

203696898048
Prime factors: 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 7 7 881
Repetitions: 19 2 2 1
Sum of repetitions equals 20?: No