BZOJ 2393 浅谈题目性质深度挖掘及容斥原理DFS写法
(助威TEAM WE) 世界真的很大 容斥原理这种东西~~虽然只是刷了几道水题而已但感觉还是要总结一波 数论的复习差不多就要结束了? 希望不要耽误太多时间吧~还要留时间给DP的第二轮复习 最后的容斥原理 看题先: description:
input:
output:
从题面上来说这道题还是比较显然的容斥了 容斥可以用DFS来实现,比起手动容斥的思路,+1,-2,+3,DFS的写法其实是先看选那些,再从选的个数来决定是+是- 完整代码: #include<stdio.h>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long dnt;
int tot=0,cnt=0,mrk[100010];
dnt L,R,ans=0;
dnt a[100010],b[100010];
void init(dnt x)
{
if(x>R) return ;
if(x) a[++tot]=x;
init(x*10+2),init(x*10+9);
}
dnt gcd(dnt a,dnt b)
{
return b==0 ? a : gcd(b,a%b);
}
dnt lcm(dnt a,dnt b)
{
return a/gcd(a,b)*b;
}
void dfs(int state,int flag,dnt delta)
{
if(state==0)
{
if(delta!=1) ans+=flag*(R/delta-(L-1)/delta);
return ;
}
dfs(state-1,flag,delta);
dnt tmp=lcm(delta,b[state]);
if(tmp<=R) dfs(state-1,-flag,tmp);
}
int main()
{
cin >> L >> R;
init(0);
sort(a+1,a+tot+1);
for(int i=1;i<=tot;i++)
{
if(mrk[i]) continue ;
b[++cnt]=a[i];
for(int j=i+1;j<=tot;j++)
if(a[j]%a[i]==0) mrk[j]=1;
}
dfs(cnt,-1,1);
cout << ans << endl;
return 0;
}
/* EL PSY CONGROO */
嗯,就是这样 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |