Bội số chung nhỏ nhất
View as PDF
Submit solution
Points:
100.00 (partial)
Time limit:
1.0s
Memory limit:
256M
Input:
stdin
Output:
stdout
Author:
Suggester:
Problem type
Allowed languages
C++, Python
Trong Toán học, bội số chung nhỏ nhất của hai số nguyên dương x, y là số nguyên dương nhỏ nhất chia hết cho cả hai số x và y. Cho hai số nguyên dương a, b (a < b); ta có số M được tính như sau: M = a × b.
Yêu cầu:
Đếm số lượng các cặp số nguyên dương (x, y) có bội số chung nhỏ nhất là M biết rằng nếu x ≠ y thì (x, y) và (y, x) được coi là hai cặp
Dữ liệu vào:
Từ dữ liệu chuẩn gồm 2 số nguyên dương a, b ≤ ~10^6~.
Kết quả ra:
Xuất ra dữ liệu chuẩn là một số nguyên dương là số cặp vừa đếm được.
Subtask:
- Subtask #1 (80 điểm): a, b ≤ ~10^6~
- Subtask #2 (20 điểm): a, b ≤ ~10^9~
Ví dụ:
input
3 4
ouput
15
Giải thích
Có 15 cặp số (1, 12); (2,12); (4,3); (4,6); (4,12); (3,4); (3, 12); (6,4); (6, 12); (12,1); (12,2); (12,3); (12,4); (12,6); (12,12); có bội số chung nhỏ nhất là 12.
Comments
include<bits/stdc++.h>
using namespace std; long int e[1000]={0}; long int c=0; void tachsnt(int n) { if(n%2==0) { while(n%2==0) { e[c]++; n=n/2; } c++; } for(long int i=3;ii<=n;i+=2) if(n%i==0) { while(n%i==0) { e[c]++; n /= i; } c++; } if(n>2) { e[c]++; c++; } } main() { long long a, b ,m; cin>>a>>b; m=ab; tachsnt(m); long int s=1; for(int i=0;i<c;i++) s=s(2e[i]+1); cout<<s<<""<