CSES - Prime Multiples | Bội số nguyên tố
Xem PDF
Điểm:
1700 (p)
Thời gian:
1.0s
Bộ nhớ:
512M
Input:
bàn phím
Output:
màn hình
Bạn được cho \(k\) số nguyên tố phân biệt \(a_1, a_2, \ldots, a_k\) và một số nguyên \(n\).
Nhiệm vụ của bạn là tính toán có bao nhiêu trong \(n\) số nguyên dương đầu tiên chia hết cho ít nhất một trong các số nguyên tố đã cho.
Input
- Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(k\).
- Dòng thứ hai có \(k\) số nguyên tố \(a_1, a_2, \ldots, a_k\).
Output
In một số nguyên: số lượng số nguyên trong trong khoảng \(1, 2, \ldots, n\) chia hết cho ít nhất một trong các số nguyên tố.
Constraints
- \(1 \leq n \leq 10^{18}\)
- \(1 \leq k \leq 20\)
- \(2 \leq a_i \leq n\)
Example
Sample input
20 2
2 5
Sample output
12
Note
\(12\) số là \(2\), \(4\), \(5\), \(6\), \(8\), \(10\), \(12\), \(14\), \(15\), \(16\), \(18\), \(20\).
Bình luận
Var n,kq:Int64;
k,i:Longint;
a:Array[0..30] of Int64;
t1:Int64;
procedure sort(l,r: longint);
var
i,j: longint;
x,y:Int64;
begin
i:=l;
j:=r;
x:=a[l+random(r-l+1)];
repeat
while a[i]<x do inc(i); while x\<a[j] do dec(j); if not(i>j) then begin y:=a[i]; a[i]:=a[j]; a[j]:=y; inc(i); j:=j-1; end; until i>j;
if l<j then
sort(l,j);
if i<r then
sort(i,r);
end;
Procedure backtracking(j,vt:Longint);
Var i:Longint;
Begin
For i:=vt to k do
Begin
If t1>n div a[i] then exit;
t1:=t1*a[i];
If j mod 2=1 then kq:=kq+n div t1
Else kq:=kq-n div t1;
If i<k then backtracking(j+1,i+1);
t1:=t1 div a[i];
End;
End;
BEGIN
Readln(n,k);
randomize;
kq:=0;
t1:=1;
For i:=1 to k do read(a[i]);
sort(1,k);
backtracking(1,1);
Writeln(kq);
readln
END.
(pascal)
cs ai AC chx giúp tôi với
ai cho e xin code đc ko ạ
Gợi ý
Backtrack + math
có cách làm nào không ạ, mình đã cày trâu bị memory
Bạn được cho \(k\) số nguyên tố phân biệt \(a_1, a_2,a_3,\dots,a_k\) và một số nguyên \(n\).
Hãy đếm trong \(n\) số nguyên dương đầu tiên, có bao nhiêu số chia hết cho ít nhất một số trong các số nguyên tố được cho.
Input
Output
Constraints
Example
Test 1
Input
Output
Note
Giải thích: \(12\) số bao gồm \(2,4,5,6,8,10,12,14,15,16,18,20\).
chưa hiểu lắm