Taigar2000

I. Бесконечный небоскрёб

Jan 11th, 2021
809
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2.  
  3. using namespace std;
  4.  
  5. int gcd(int a, int b, int &x, int &y) {
  6.     if (a == 0) {
  7.         x = 0; y = 1;
  8.         return b;
  9.     }
  10.     int x1, y1;
  11.     int d = gcd (b%a, a, x1, y1);
  12.     x = y1 - (b / a) * x1;
  13.     y = x1;
  14.     return d;
  15. }
  16.  
  17. int main(){
  18.     int n, p;
  19.     cin >> n >> p;
  20.     int r = 0;
  21.     for(int i = 1; i <= n; ++i){
  22.         int x, y;
  23.         gcd(i, p, x, y);
  24.         if(x < 0){
  25.             x = (-x)*(p-1)%p;
  26.         }
  27.         r += x;
  28.     }
  29.     cout << r;
  30.     return 0;
  31. }
RAW Paste Data