Районная олимпиада по информатике. 2016-2017 учебный год.

Задача C. Остатки

Ограничение по времени:

2 секунда

Ограничение по памяти:

64 мегабайта

Даны целые числа $a,$ $b$ и $n.$ Требуется найти количество целых чисел $x$ таких, что $0 \le x < n$ и число $a\cdot x$ при делении на $n$ дает остаток $b.$

Формат входного файла

Единственная строка входного файла содержит три целых числа разделенных пробелом: $a,$ $b$ и $n$ $(0 \le n \le 100000,$ $0 \le a, b < 100000).$

Формат выходного файла

Выведите ответ к задаче.

Примеры:

Вход

3 0 6

Ответ

3

Комментарий/решение

показать/скрыть код

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int main() {
    ll a,b,n;
    cin >> a >> b >> n;
    int ans=0;
    for (int x=0; x<n; x++) if ((a*x)%n==b) ans++;
    cout << ans;
}

C++

Copy

показать/скрыть код

with open('input') as file:
    data, sc = file.read().split('\n')[0].split(), 0

    for i in range(1, int(data[2]) + 1):
        if int(data[0]) * i % int(data[2]) == int(data[1]): sc += 1

with open('output', 'w') as file: file.write(str(sc))

C++

Copy

DELETED

показать/скрыть код

#include <iostream>
#define speed ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;
int main() {
    speed;
    long long a, b, n;
    cin >> a >> b >> n;
    long long cnt = 0;
    for(long long x = 0; x < n; x++) {
        if((a * x) % n == b) {
            cnt++;
        }
    }
    cout << cnt;
}

C++

Copy

показать/скрыть код

C++

Copy

#include<bits/stdc++.h>

using namespace std ;

int main () {

int n , m , k , cnt = 0 ;

cin >> n >> m >> k ;

for(int i = 1 ; i <= k ; i++){

if(n * i % k == m){

cnt++ ;

}

}

cout << cnt ;

}

#include<bits/stdc++.h>

using namespace std;

#define ll long long int

int main () {

ios_base::sync_with_stdio(0);

cin.tie(0);cout.tie(0);

ll a, b,n, ans=0;

cin>>a>>b>>n;

for(ll i=0;i<n;i++)

if((i*a)%n==b)ans++;

cout<<ans;

}

a,b,n=map(int,input().split())

k=0

for x in range(n):

if a*x%n==b:

k+=1

print(k)

a,b,n = map(int,input().split())

c=0

for x in range(n):

if a*x%n==b:

c+=1

print(c)