codeforces-scrape

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

1242A.md (1589B)


      1 Source: https://codeforces.com/problemset/problem/1242/A
      2 
      3 A. Tile Painting
      4 
      5 time limit per test
      6 
      7 1 second
      8 
      9 memory limit per test
     10 
     11 256 megabytes
     12 
     13 input
     14 
     15 standard input
     16 
     17 output
     18 
     19 standard output
     20 
     21 Ujan has been lazy lately, but now has decided to bring his yard to good shape. First, he decided to paint the path from his house to the gate.
     22 
     23 The path consists of $n$ consecutive tiles, numbered from $1$ to $n$. Ujan will paint each tile in some color. He will consider the path aesthetic if for any two different tiles with numbers $i$ and $j$, such that $|j - i|$ is a divisor of $n$ greater than $1$, they have the same color. Formally, the colors of two tiles with numbers $i$ and $j$ should be the same if $|i-j| \gt 1$ and $n \bmod |i-j| = 0$ (where $x \bmod y$ is the remainder when dividing $x$ by $y$).
     24 
     25 Ujan wants to brighten up space. What is the maximum number of different colors that Ujan can use, so that the path is aesthetic?
     26 
     27 Input
     28 
     29 The first line of input contains a single integer $n$ ($1 \leq n \leq 10^{12}$), the length of the path.
     30 
     31 Output
     32 
     33 Output a single integer, the maximum possible number of colors that the path can be painted in.
     34 
     35 Examples
     36 
     37 Input
     38 
     39 ```
     40 4
     41 ```
     42 
     43 Output
     44 
     45 ```
     46 2
     47 ```
     48 
     49 Input
     50 
     51 ```
     52 5
     53 ```
     54 
     55 Output
     56 
     57 ```
     58 5
     59 ```
     60 
     61 Note
     62 
     63 In the first sample, two colors is the maximum number. Tiles $1$ and $3$ should have the same color since $4 \bmod |3-1| = 0$. Also, tiles $2$ and $4$ should have the same color since $4 \bmod |4-2| = 0$.
     64 
     65 In the second sample, all five colors can be used.
     66 
     67  ![](https://espresso.codeforces.com/f6b35779803c9f7a5fef85021985288936e853f8.png)