codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

150A.md (1907B)


      1 Source: https://codeforces.com/problemset/problem/150/A
      2 
      3 A. Win or Freeze
      4 
      5 time limit per test
      6 
      7 2 seconds
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 stdin
     16 
     17 output
     18 
     19 stdout
     20 
     21 You can't possibly imagine how cold our friends are this winter in Nvodsk! Two of them play the following game to warm up: initially a piece of paper has an integer *q*. During a move a player should write any integer number that is a non-trivial divisor of the last written number. Then he should run this number of circles around the hotel. Let us remind you that a number's divisor is called non-trivial if it is different from one and from the divided number itself.
     22 
     23 The first person who can't make a move wins as he continues to lie in his warm bed under three blankets while the other one keeps running. Determine which player wins considering that both players play optimally. If the first player wins, print any winning first move.
     24 
     25 Input
     26 
     27 The first line contains the only integer *q* (1 ≤ *q* ≤ 1013).
     28 
     29 Please do not use the %lld specificator to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specificator.
     30 
     31 Output
     32 
     33 In the first line print the number of the winning player (1 or 2). If the first player wins then the second line should contain another integer — his first move (if the first player can't even make the first move, print 0). If there are multiple solutions, print any of them.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 6
     41 ```
     42 
     43 Output
     44 
     45 ```
     46 2
     47 ```
     48 
     49 Input
     50 
     51 ```
     52 30
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 1  
     59 6
     60 ```
     61 
     62 Input
     63 
     64 ```
     65 1
     66 ```
     67 
     68 Output
     69 
     70 ```
     71 1  
     72 0
     73 ```
     74 
     75 Note
     76 
     77 Number 6 has only two non-trivial divisors: 2 and 3. It is impossible to make a move after the numbers 2 and 3 are written, so both of them are winning, thus, number 6 is the losing number. A player can make a move and write number 6 after number 30; 6, as we know, is a losing number. Thus, this move will bring us the victory.