there is a very easy process.apply inclusion-exclusion principle & then backtrack.your code is so complicated. see my 10 line code. #include #define ll long long using namespace std; int ara[15]; ll N,m; ll LCM(ll a,ll b) { return a/__gcd(a,b)*b; } ll backtrack(ll n,ll div) { if(n==m) return (N/div); return backtrack(n+1,div)-backtrack(n+1,LCM(div,ara[n])); } int main() { while(cin>>N>>m) { for(int i=0;i>ara[i]; cout<<backtrack(0,1)<<endl; } return 0; }
there is a very easy process.apply inclusion-exclusion principle & then backtrack.your code is so complicated.
回覆刪除see my 10 line code.
#include
#define ll long long
using namespace std;
int ara[15];
ll N,m;
ll LCM(ll a,ll b)
{
return a/__gcd(a,b)*b;
}
ll backtrack(ll n,ll div)
{
if(n==m) return (N/div);
return backtrack(n+1,div)-backtrack(n+1,LCM(div,ara[n]));
}
int main()
{
while(cin>>N>>m)
{
for(int i=0;i>ara[i];
cout<<backtrack(0,1)<<endl;
}
return 0;
}
Hi Khan Hasan:
刪除Thank you for your comment!
Backtrack seems a better way to do inclusion-exclusion.
I'll try it next time.
But your code is incomplete in the comment.