Product Codes - Ma hang hoa (But Wait, There Are Some Changes Version)
Company E specializes in mass-producing products on an assembly line. When products are placed on the conveyor belt for the final finishing steps, each product is assigned an ID code for tracking. The ID of each product is a positive integer corresponding to its sequential position as it enters the conveyor belt.
Due to overdue maintenance, two processing stages on the conveyor belt are technically faulty. In the first stage, every \(a\)-th product processed is defective. In the second stage, every \(b\)-th product processed is defective. Consequently, any product with an ID divisible by \(a\) or divisible by $b$ is defective, and the automated system rejects it. During a shift, an operator wants to know how many defective products there are among the first \(N\) products produced.
Input
- A single line containing three positive integers \(a, b, N \ (2 \le a, b \le 10^9; 2 \le N \le 10^{18})\).
Output
- A single integer representing the total number of defective products.
Scoring
- Subtask 1 (70%): \(N \le 10^6\).
- Subtask 2 (30%): No additional constraints.
Examples
Example 1
input
2 5 23
output
13
Explanation
The defective products with IDs not exceeding 23 are: 2, 4, 5, 6, 8, 10, 12, 14, 15, 16, 18, 20, 22 (a total of 13 defective products).
Comments