Обсуждение @ 2102. Миша и криптография @ Timus Online Judge

TLE22

Послано Kogut.Ivan 20 ноя 2016 14:02

I get TLE on 22 test. What can you advise?

Re: TLE22

Послано Felix_Mate 20 ноя 2016 21:22

1)In solution you must find all primes <= 10^7.
2)You must use that n<=10^18.

Re: TLE22

Послано esbybb 21 ноя 2016 08:57

1. find all primes up to 2 millions
2. if remainder > 2 millions, check if it is a prime

Re: TLE22

Послано esbybb 21 ноя 2016 08:57

remaining typo

Re: TLE22

Послано Kogut.Ivan 21 ноя 2016 21:40

Why do you take this number?

Re: TLE22

Послано Zarhri 9 июл 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

Послано Dmitry Shatunow 4 ноя 2019 22:16

Edited by author 05.11.2019 20:56

Edited by author 05.11.2019 20:57

Обсуждение задачи 2102. Миша и криптография