codeforces-scrape

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

284A.md (1384B)


      1 Source: https://codeforces.com/problemset/problem/284/A
      2 
      3 A. Cows and Primitive Roots
      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 The cows have just learned what a primitive root is! Given a prime *p*, a primitive root ![](https://espresso.codeforces.com/f203bd9f1553a2d666452cec7d6f1f4f02a817fb.png) is an integer *x* (1 ≤ *x* < *p*) such that none of integers *x* - 1, *x*2 - 1, ..., *x**p* - 2 - 1 are divisible by *p*, but *x**p* - 1 - 1 is.
     22 
     23 Unfortunately, computing primitive roots can be time consuming, so the cows need your help. Given a prime *p*, help the cows find the number of primitive roots ![](https://espresso.codeforces.com/f203bd9f1553a2d666452cec7d6f1f4f02a817fb.png).
     24 
     25 Input
     26 
     27 The input contains a single line containing an integer *p* (2 ≤ *p* < 2000). It is guaranteed that *p* is a prime.
     28 
     29 Output
     30 
     31 Output on a single line the number of primitive roots ![](https://espresso.codeforces.com/f203bd9f1553a2d666452cec7d6f1f4f02a817fb.png).
     32 
     33 Examples
     34 
     35 Input
     36 
     37 ```
     38 3
     39 ```
     40 
     41 Output
     42 
     43 ```
     44 1
     45 ```
     46 
     47 Input
     48 
     49 ```
     50 5
     51 ```
     52 
     53 Output
     54 
     55 ```
     56 2
     57 ```
     58 
     59 Note
     60 
     61 The only primitive root ![](https://espresso.codeforces.com/3722298ba062e95b18705d1253eb4e5d31e3b2d1.png) is 2.
     62 
     63 The primitive roots ![](https://espresso.codeforces.com/1d85c6a17ef1c42b53cf94d00bc49a7ac458fd58.png) are 2 and 3.