Đếm ước nguyên tố
View as PDF
Submit solution
Points:
100.00 (partial)
Time limit:
1.0s
Memory limit:
1G
Input:
stdin
Output:
stdout
Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text
Cho hai số nguyên dương ~M~ và ~N~ (1 ≤ ~M~ ≤ ~N~ ≤ 60000) và số ~S~ được xác định bằng công thức sau: ~S~ = ~n~!/(~m~!(~n~−~m~)!)
Yêu cầu: Đếm số lượng ước nguyên tố của ~S~
Input: gồm một dòng ghi hai số ~N~ và ~M~ cách nhau một dấu cách.
Output: gồm một dòng ghi 1 số duy nhất là số lượng ước nguyên tố của ~S~.
Ví dụ:
Input
7 3
Output
2
Comments
just dem uoc
n!/m!(n-m)! vì n>m nên sẽ rút gọn đc chẳng hạn ntn: (1234567)/(1231234)=(4567)/(1234) vẫn tiếp tục cái ví dụ trên (4567)/(1234)=(2^3537)/(2^33) dễ thấy nếu số mũ của số nguyên tố trên tử lớn hơn dưới mẫu thì đó là ước nguyên tố của S vậy đếm phân phối tử,mẫu nếu đếm phân phối trên tử lớn hơn thì kq+1 code:
include<bits/stdc++.h>
using namespace std; int c[100000]={0}; int c1[100000]={0}; int main(){ int n,m; cin>>n>>m; for(int i=m+1;i<=n;i++){ int t=i; int k=2; while(t!=1){ if(t%k==0){ c[k]++; t/=k; } else{ k++; } } } for(int i=2;i<=n-m;i++){ int t=i; int k=2; while(t!=1){ if(t%k==0){ c1[k]++; t/=k; } else{ k++; } } } int d=0; for(int i=2;i<=100000;i++){ if(c[i]>c1[i]){ d++; } } cout<<d; return 0;
}
Hướng giải bài này là gì vậy ạ, nếu tính như thông thường thì tổ hợp số lớn k tính dc và bị TLE :((