幸运数字(number)
Time Limit:1000ms Memory Limit:64MB
题目描述
LYK 最近运气很差，例如在 NOIP 初赛中仅仅考了 90 分，刚刚卡进复赛，于是它决定使
用一些方法来增加自己的运气值。
它觉得，通过收集幸运数字可以快速的增加它的 RP 值。
它给幸运数字下了一个定义： 如果一个数 x 能被 3 整除或被 5 整除或被 7 整除， 则这个
数为幸运数字。
于是它想让你帮帮它在 L~R 中存在多少幸运数字。
输入格式(number.in)
第一行两个数 L,R。
输出格式(number.out)
一个数表示答案。
输入样例
10 15
输出样例
4
数据范围
对于 50%的数据 1<=L<=R<=10^5。
对于 60%的数据 1<=L<=R<=10^9。
对于 80%的数据 1<=L<=R<=10^18。
对于 90%的数据 1<=L<=R<=10^100。
对于另外 10%的数据 L=1，1<=R<=10^100。
对于 100%的数据 L，R 没有前导 0。
/*
代码太长，copy from other's
容斥原理
对于1~x中，ans=x/3+x/5+x/7-x/15-x/21-x/35+x/105
注意高精度时应该先把该加的都加上，在进行减法，这样可以避免出现负数。
*/
#include<cstdio>
#include<iostream>
#include<cstring>
#define N 200
using namespace std;
char s[N];int a1[N],b1[N],c1[N];
struct node
{
int a[N],len;
void clear()
{
memset(a,,sizeof(a));len=;
}
};node s1,s2,ans;
node jia(node x,node y)
{
node c;c.clear();
memset(a1,,sizeof(a1));
memset(b1,,sizeof(b1));
memset(c1,,sizeof(c1));
for(int i=;i<=x.len;i++)a1[i]=x.a[x.len-i+];
for(int i=;i<=y.len;i++)b1[i]=y.a[y.len-i+];
int len=max(x.len,y.len);
for(int i=;i<=len;i++)
{
c1[i]+=a1[i]+b1[i];
c1[i+]+=c1[i]/;
c1[i]%=;
}
if(c1[len+])len++;
c.len=len;
for(int i=len;i>=;i--)c.a[i]=c1[len-i+];
return c;
}
node jian(node x,node y)
{
node c;c.clear();
memset(a1,,sizeof(a1));
memset(b1,,sizeof(b1));
memset(c1,,sizeof(c1));
for(int i=;i<=x.len;i++)a1[i]=x.a[x.len-i+];
for(int i=;i<=y.len;i++)b1[i]=y.a[y.len-i+];
int len=max(x.len,y.len);
for(int i=;i<=len;i++)
{
if(a1[i]>=b1[i])c1[i]=a1[i]-b1[i];
else
{
c1[i]=a1[i]+-b1[i];
a1[i+]--;
}
}
int p=len;
while(c1[p]==)p--;
for(int i=p;i>=;i--)c.a[++c.len]=c1[i];
return c;
}
node chu(node x,int b)
{
node c;c.clear();
memset(a1,,sizeof(a1));
int xx=;
for(int i=;i<=x.len;i++)
{
a1[i]=(xx*+x.a[i])/b;
xx=xx*+x.a[i]-a1[i]*b;
}
int len=;
while(!a1[len]&&len)len++;
for(int i=len;i<=x.len;i++)
c.a[++c.len]=a1[i];
return c;
}
void init()
{
s1.a[s1.len]--;
for(int i=s1.len;i>=;i--)
{
if(s1.a[i]>=)break;
else
{
s1.a[i]+=;
s1.a[i-]--;
}
}
if(!s1.a[])
{
s1.len--;
for(int i=;i<=s1.len;i++)
s1.a[i]=s1.a[i+];
}
}
int main()
{
//freopen("number.in","r",stdin);
//freopen("number.out","w",stdout);
cin>>s;s1.len=strlen(s);
for(int i=;i<=s1.len;i++)s1.a[i]=s[i-]-'';
cin>>s;s2.len=strlen(s);
for(int i=;i<=s2.len;i++)s2.a[i]=s[i-]-'';
init();
ans=chu(s2,);
ans=jia(ans,chu(s2,));
ans=jia(ans,chu(s2,));
ans=jia(ans,chu(s2,));
ans=jia(ans,chu(s1,));
ans=jia(ans,chu(s1,));
ans=jia(ans,chu(s1,));
ans=jian(ans,chu(s2,));
ans=jian(ans,chu(s2,));
ans=jian(ans,chu(s2,));
ans=jian(ans,chu(s1,));
ans=jian(ans,chu(s1,));
ans=jian(ans,chu(s1,));
ans=jian(ans,chu(s1,));
for(int i=;i<=ans.len;i++)
printf("%d",ans.a[i]);
return ;
}
思路：容斥原理ans=（r/3+r/5+r/7-r/15-r/35-r/21+r/105）-（(l-1)/3+(l-1)/5+(l-1)/7-(l-1)/15-(l-1)/35-(l-1)/21+(l-1)/105）