How can we prove this : no of unique outputs to (i*j)%k where i can be any number j and k are known is k/__gcd(k,j);

# | User | Rating |
---|---|---|

1 | tourist | 3947 |

2 | jiangly | 3740 |

3 | Radewoosh | 3652 |

4 | Benq | 3626 |

5 | jqdai0815 | 3620 |

6 | orzdevinwang | 3612 |

7 | ecnerwala | 3587 |

8 | Geothermal | 3569 |

8 | cnnfls_csy | 3569 |

10 | ksun48 | 3485 |

# | User | Contrib. |
---|---|---|

1 | awoo | 162 |

2 | maomao90 | 160 |

3 | adamant | 156 |

4 | atcoder_official | 155 |

5 | nor | 153 |

5 | cry | 153 |

7 | maroonrk | 152 |

8 | SecondThread | 148 |

8 | -is-this-fft- | 148 |

10 | Petr | 146 |

How can we prove this : no of unique outputs to (i*j)%k where i can be any number j and k are known is k/__gcd(k,j);

↑

↓

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/16/2024 06:57:54 (j1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

You need to find for which

athere exists a solution toij≡a(modk) whereiis a variable. Obviously if (k,j) = 1 thenjhas an inversemodjso for anya<kthere exists an unique solution.Now suppose (

k,j) =d! = 1, then your equation becomes equivalent to finding anlsuch thatij=lk+aorij+ ( -l)k=a. A pairi,lexists if and only if , soa=dxwherexhas some random value. Now you haved*x<ksox<k/d, soxcan range from 0 tok/d- 1, so there are exactlyk/dvariables for which there exists a solution.