Đế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

Please read the guidelines before commenting.



  • 0
    cc  commented on April 25, 2024, 11:45 a.m.

    just dem uoc


  • -3
    phongtapdev  commented on June 11, 2023, 4:44 a.m.

    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;

    }


  • -1
    HoangTrong  commented on May 18, 2023, 2:39 a.m.

    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 :((