CF 104820C - Оценочное
We are given two grading systems: one uses scores from 1 to n, the other uses scores from 1 to m. Some scores in the first system are considered equivalent to some scores in the second system, but the problem does not give us arbitrary pairs.
CF 104820C - \u041e\u0446\u0435\u043d\u043e\u0447\u043d\u043e\u0435
Rating: -
Tags: -
Solve time: 1m 5s
Verified: yes
Solution
Problem Understanding
We are given two grading systems: one uses scores from 1 to n, the other uses scores from 1 to m. Some scores in the first system are considered equivalent to some scores in the second system, but the problem does not give us arbitrary pairs. Instead, the structure implied by the samples is that equivalence behaves like a uniform scaling between the two systems: values that correspond to the same relative “quality level” align whenever they represent the same fraction of the maximum.
From this viewpoint, a score x in the m-scale corresponds to some score y in the n-scale if both represent the same normalized position, meaning x / m = y / n. Such a pair exists exactly when x is a multiple of m / gcd(n, m), because the shared fraction grid between the two scales is determined by their greatest common divisor.
The task reduces to counting how many integers x in the range [1, m] actually appear in this shared grid.
The constraints go up to 10^18 for both n and m, so any solution that iterates over values or constructs arrays is impossible. Even O(min(n, m)) is far too large. The solution must reduce the problem to a constant number of arithmetic operations on big integers.
A subtle edge case appears when n and m are coprime. Then the only shared normalized points are the endpoints 0 and 1 in fractional form, which corresponds to only the value m itself in the m-scale. For example, with n = 3 and m = 4, only one value matches.
Another edge case is when n = m. In that case every score matches itself, so the answer is m. A naive interpretation that counts only “properly mapped internal points” would incorrectly miss endpoints.
Approaches
If we try to simulate equivalences directly, we would need to check for every x in [1, m] whether there exists y in [1, n] such that x / m = y / n. Checking this condition requires either rational reduction or scanning all candidates. Even a single pass over m up to 10^18 is impossible.
The key observation is that equality of fractions x / m and y / n implies cross multiplication: x * n = y * m. Any valid pair corresponds to a shared rational point on both grids. The set of all such points is exactly the lattice generated by the least common multiple structure of n and m.
The spacing between consecutive matching x-values is m / gcd(n, m). This comes from rewriting the equality as x = k * (m / gcd(n, m)), where k ranges over all integers such that the corresponding y stays within [1, n]. Since k can range from 1 to gcd(n, m), there are exactly gcd(n, m) valid values of x.
Thus the problem reduces to computing gcd(n, m), which directly counts how many equivalence points exist in the m-scale.
| Approach | Time Complexity | Space Complexity | Verdict |
|---|---|---|---|
| Brute Force enumeration of x in [1, m] | O(m) | O(1) | Too slow |
| Optimal using gcd structure | O(log min(n, m)) | O(1) | Accepted |
Algorithm Walkthrough
- Read the two integers n and m. These define two discrete scales that we compare through proportional alignment.
- Compute g = gcd(n, m). This captures the maximum step size that preserves proportional equality between the two scales.
- Recognize that each valid matching score in the m-scale must be of the form k * (m / g), where k is an integer from 1 to g.
- Conclude that the number of valid scores is exactly g.
The reason this enumeration works is that dividing both n and m by their gcd reduces the fraction n/m to lowest terms. The alignment points between the two sequences occur exactly at multiples of this reduced step.
Why it works
Any valid correspondence satisfies x / m = y / n. Rearranging gives x * n = y * m. Let g = gcd(n, m), and write n = g * n' and m = g * m' where n' and m' are coprime. The equation becomes x * n' = y * m'. Since n' and m' share no common factors, x must be divisible by m' and y must be divisible by n'. This forces x = k * m' and y = k * n' for some integer k. The constraints 1 ≤ x ≤ m and 1 ≤ y ≤ n imply k ranges exactly from 1 to g, producing g valid values.
Python Solution
import sys
input = sys.stdin.readline
from math import gcd
n, m = map(int, input().split())
print(gcd(n, m))
The entire solution rests on computing the greatest common divisor. The math module implementation uses an efficient Euclidean algorithm, which is appropriate for values up to 10^18.
The only subtlety is that no additional normalization or boundary handling is required. Both endpoints are implicitly included because gcd counting already accounts for full alignment points, including the maximum score m when it corresponds to n.
Worked Examples
Example 1: n = 5, m = 10
We compute g = gcd(5, 10) = 5.
| Step | Value |
|---|---|
| n | 5 |
| m | 10 |
| gcd(n, m) | 5 |
| answer | 5 |
The five matching points correspond to fractions 1/5, 2/5, 3/5, 4/5, and 5/5, which map to 2, 4, 6, 8, and 10 in the 10-scale. This confirms that all evenly spaced proportional levels are counted.
Example 2: n = 3, m = 4
We compute g = gcd(3, 4) = 1.
| Step | Value |
|---|---|
| n | 3 |
| m | 4 |
| gcd(n, m) | 1 |
| answer | 1 |
Only the endpoint 4 corresponds to a valid shared fraction (1), so only one score exists in the m-scale.
Complexity Analysis
| Measure | Complexity | Explanation |
|---|---|---|
| Time | O(log min(n, m)) | Euclidean gcd computation reduces the problem in logarithmic steps |
| Space | O(1) | only a few integers are stored |
The input bounds up to 10^18 make arithmetic operations the only viable approach, and the gcd computation comfortably fits within constraints.
Test Cases
import sys, io
from math import gcd
def solve():
n, m = map(int, sys.stdin.readline().split())
print(gcd(n, m))
def run(inp: str) -> str:
old_stdin = sys.stdin
sys.stdin = io.StringIO(inp)
out = io.StringIO()
old_stdout = sys.stdout
sys.stdout = out
solve()
sys.stdout = old_stdout
sys.stdin = old_stdin
return out.getvalue().strip()
assert run("5 10") == "5"
assert run("1 1") == "1"
assert run("3 4") == "1"
assert run("6 9") == "3"
assert run("10 1000000000000000000") == "10"
assert run("7 13") == "1"
| Test input | Expected output | What it validates |
|---|---|---|
| 5 10 | 5 | basic proportional alignment |
| 1 1 | 1 | minimal case |
| 3 4 | 1 | coprime case |
| 6 9 | 3 | non-trivial gcd |
| 10 10^18 | 10 | large imbalance stress |
Edge Cases
When n = m, the gcd equals n, so the answer is n. For example, input 7 7 produces gcd(7, 7) = 7, meaning all seven scores in the m-scale correspond directly to identical positions in the n-scale.
When n and m are coprime, such as 7 and 13, gcd is 1. The algorithm returns 1, reflecting that only the endpoints align in normalized space. The computation does not need any special handling because the Euclidean algorithm naturally reduces the pair to this case.
When one value is extremely large and the other small, such as 10 and 10^18, the gcd still captures the full structure. The Euclidean algorithm quickly reduces 10^18 modulo 10, leaving gcd 10.