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

TLE22
Posted by Kogut.Ivan 20 Nov 2016 14:02
I get TLE on 22 test. What can you advise?
Re: TLE22
Posted by Felix_Mate 20 Nov 2016 21:22
1)In solution you must find all primes <= 10^7.
2)You must use that n<=10^18.
Re: TLE22
Posted by esbybb 21 Nov 2016 08:57

1. find all primes up to 2 millions
2. if remainder > 2 millions, check if it is a prime
Re: TLE22
Posted by esbybb 21 Nov 2016 08:57
remaining typo
Re: TLE22
Posted by Kogut.Ivan 21 Nov 2016 21:40
Why do you take this number?
Re: TLE22
Posted by Zarhri 9 Jul 2017 15:04
big number N = X*Y*(p1*p2*p3*....*p18) = X*Y*(A)
A = at least 2^18 = 262144
So, X*Y = at most 10^18 / 2^18 = 3 814 697 266 000
So either X or Y is less than 10^7
Re: TLE22
Posted by Dmitry Shatunow 4 Nov 2019 22:16
Edited by author 05.11.2019 20:56

Edited by author 05.11.2019 20:57