単純反発定理-hdu-1796-How many integers can you find
1722 ワード
タイトルリンク:
http://acm.hdu.edu.cn/showproblem.php?pid=1796
テーマ:
1つのnを与え、m個の数を与え、1~nのうちmのある数で割り切れる数の個数を求める.
問題解決の考え方:
簡単に反発し,説明しない.
まずm個に対して0を除いて、それから数を並べて、それから反発します.前の最小公倍数を求めるたびに.
注意:
10 2
2 11 keys:4
10 2
11 2 keys:4
コード:
http://acm.hdu.edu.cn/showproblem.php?pid=1796
テーマ:
1つのnを与え、m個の数を与え、1~nのうちmのある数で割り切れる数の個数を求める.
問題解決の考え方:
簡単に反発し,説明しない.
まずm個に対して0を除いて、それから数を並べて、それから反発します.前の最小公倍数を求めるたびに.
注意:
10 2
2 11 keys:4
10 2
11 2 keys:4
コード:
#include<iostream>
#include<cmath>
#include<cstdio>
#include<cstdlib>
#include<string>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#define eps 1e-6
#define INF 0x1f1f1f1f
#define PI acos(-1.0)
#define ll __int64
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
//freopen("data.in","r",stdin);
//freopen("data.out","w",stdout);
ll pp[15],cnt,n;
ll ans;
ll gcd(ll a,ll b)
{
if(a%b==0)
return b;
return gcd(b,a%b);
}
ll lcm(ll a,ll b)
{
return a/gcd(a,b)*b;
}
void dfs(ll la,ll pos,ll flag)
{
if(pos>cnt)
return ;
for(int i=pos;i<=cnt;i++)
{
ll t=(n-1)/lcm(la,pp[i]);
if(flag)
ans+=t;
else
ans-=t;
dfs(lcm(la,pp[i]),i+1,flag^1);
}
}
int main()
{
while(~scanf("%I64d",&n))
{
cnt=0;
int m;
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
ll a;
scanf("%I64d",&a);
if(a)
pp[++cnt]=a;
}
sort(pp+1,pp+cnt+1); //
ans=0;
dfs(1,1,1);
printf("%I64d
",ans);
}
return 0;
}