Hãy luôn nhớ cảm ơn và vote 5*
nếu câu trả lời hữu ích nhé!
đã AC dù hơi khổ =)
// carot15
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll nmax=5e5+5;
const ll mod=1e9+7;
ll check(ll n){
if(n<=1) return 0;
if(n<=3) return 1;
if(n%2==0||n%3==0) return 0;
for(ll i=5;i*i<=n;i+=6)
if(n%i==0||n%(i+2)==0)
return 0;
return 1;
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
// freopen("INPUT.TXT", "r", stdin);
// freopen("OUTPUT.TXT", "w", stdout);
ll n,k,ans=0;
cin>>n>>k;
vector<ll> p;
if (check(n)){
cout<<k-k/n;
return 0;
}
for (int i=2;i<=sqrt(n);i++)
if (n%i==0){
if (check(i))
p.push_back(i);
ll x=n/i;
if (x==i) continue;
if (check(x))
p.push_back(x);
}
for (ll i=0;i<p.size();i++) {
ans+=k/p[i];
for (int e=i+1;e<p.size();e++){
ans-=k/(p[i]*p[e]);
for (int f=e+1;f<p.size();f++){
ans+=k/(p[i]*p[e]*p[f]);
for (int j=f+1;j<p.size();j++){
ans-=k/(p[i]*p[e]*p[f]*p[j]);
for (int l=j+1;l<p.size();l++){
ans+=k/(p[i]*p[e]*p[f]*p[j]*p[l]);
for (int m=l+1;m<p.size();m++){
ans-=k/(p[i]*p[e]*p[f]*p[j]*p[l]*p[m]);
}
}
}
}
}
}
cout<<k-ans;
}
Hãy giúp mọi người biết câu trả lời này thế nào?
Bảng tin
0
61
0
Tại sao dùng có 6 vòng for vậy bạn mình không hiểu lắm giải thích mình với, mình nghĩ số vòng for bằng số phần từ mảng p chứ
268
3759
203
đây là mình dùng công thức đếm số chia hết cho các ước nguyên tố của n trong đoạn vd: đếm số chia hết cho 2 hoặc 3 trong đoạn từ 1>k thì số chia hết = k/2 + k/3 - k/6 vì phải loại đi ước chung
0
61
0
mình hiểu chỗ đó rồi, ý mình là sao bạn dùng có 6 vòng for vẫn ac p.size() có thể lớn hơn 6 mà
268
3759
203
test yếu bạn ạ ban đầu mình thử 8 vòng cơ =) nếu đúng thì phải là 8
268
3759
203
vì sqrt(k)=1e6 ít hơn 8 số nto đầu nhân lại
268
3759
203
6 vòng cho nó ngắn =)
268
3759
203
à đâu mình nhầm =)
268
3759
203
=) kệ đi bạn ạ 12 vòng vẫn ac