#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
#include <thread>
using namespace std;

const int oo_min=0xc0c0c0c0,oo_max=0x3f3f3f3f;

namespace dts
{
    typedef long long ll;
    
    ll n,a,b;
    ll rec[15+1];
    
    ll calc(ll a,ll b,ll key)
    {
        ll l,r;
        if (a%key!=0)
            l=((a/key)+1)*key;
        else
            l=a;
        if (b%key!=0)
            r=(b/key)*key;
        else
            r=b;
        if (l<=r)
            return (r-l)/key+1;
        else
            return 0;
    }
    
    ll gcd(ll a,ll b)
    {
        if (b==0)
            return a;
        else
            return gcd(b,a%b);
    }
    
    ll lcm(ll a,ll b)
    {
        return a*b/gcd(a,b);
    }
    
    void dfs(ll pos,ll num,ll sig,ll *ans)
    {
        *ans+=sig*calc(a,b,num);
        for (ll i=pos+1;i<=n;i++)
            dfs(i,lcm(num,rec[i]),-sig,ans);
    }
    
    ll work()
    {
        ll temp=8,ans=0;
        dfs(0,temp,1,&ans);
        return ans;
    }
    
    void main()
    {
        while (~scanf("%lld",&n))
        {
            for (ll i=1;i<=n;i++)
                scanf("%lld",&rec[i]);
            scanf("%lld%lld",&a,&b);
            printf("%lld\n",work());
        }
    }
};

int main()
{
    dts::main();
}

尽量易懂

#include<cstdio>
#include<algorithm>
#define LL long long
using namespace std;
const int N=25;
LL n,a,b;
LL ai[N];
int Gcd(int a,int b){
return b==0?a:Gcd(b,a%b);
}
void Dfs(LL k,LL las,LL &sum,LL num){
int pos=num;
for(int i=las+1;i<=n;i++){
int g=Gcd(num,ai[i]);
if (num/g*ai[i]>b) continue;

else{
num=num/g*ai[i];
if (k&1) sum+=(b/num)-(a/num);
else sum-=(b/num)-(a/num);
Dfs(k+1,i,sum,num);
num=pos;
}
}
return;

}
int main(){
scanf("%lld",&n);
for(int i=1;i<=n;i++){
scanf("%lld",&ai[i]);
if (ai[i]==1||ai[i]==2||ai[i]==4||ai[i]==8){
printf("0");
return 0;

}

}
scanf("%lld %lld",&a,&b);
LL sum=0;
Dfs(1,0,sum,8);
printf("%lld",(b/8)-(a/8)-sum);
return 0;

}

水题
C++
#include<cstdio>
#include<iostream>
#define LL long long
using namespace std;
LL n,num[20],a,b,ans;
LL lcm(LL a,LL b,LL x,LL y)
{
if(b==0)
return x*y/a;
return lcm(b,a%b,x,y);
}
void dfs(LL i,LL sum,LL cnt)
{
if(i>n)
{
if(cnt%2)
ans-=(b/sum-a/sum);
else
ans+=(b/sum-a/sum);
return;
}
dfs(i+1,sum,cnt);
dfs(i+1,lcm(sum,num[i],sum,num[i]),cnt+1);
}
int main()
{
scanf("%I64d",&n);
for(int i=1;i<=n;i++)
scanf("%I64d",&num[i]);
scanf("%I64d%I64d",&a,&b);
dfs(1,8,0);
printf("%I64d",ans);
return 0;
}


//题解真是难懂（看来要去学语文了。），不如自己去想。

奇数的减去 偶数的加上 。 不要忘了8 //前3个点似乎不用8...
Dfs 枚举那几个数 Gcd 求最大公约数来求最小公倍数。

var
    i,n,a,b,dis,point:longint;
    ans:int64;
    data,g:array[0..15]of int64;
    flag:array[0..10000]of boolean;

function gcd(a,b:int64):int64;
begin
    if b=0 then exit(a) else
        exit(gcd(b,a mod b));
end;

procedure check(dis:longint);
var
    i:longint;
    tmp1,tmp2:int64;
begin
    tmp1:=g[1]*8;
    tmp2:=tmp1 div gcd(g[1],8);
    for i:=2 to dis do
    begin
        tmp1:=tmp2*g[i];
        tmp2:=tmp1 div gcd(tmp2,g[i]);
        if tmp2>b then exit;
    end;
    if (dis and 1=1) then ans:=ans-((b div tmp2)-((a-1)div tmp2)) else
        ans:=ans+((b div tmp2)-((a-1)div tmp2));

end;

procedure Dfs(head,dep,dis:longint);
var
    i:longint;
begin
    if dep=dis+1 then
    begin
        check(dis);
        exit;
    end;
    if head>n then exit;
    for i:=head to n do
    begin
        g[dep]:=data[i];
        Dfs(i+1,dep+1,dis)
    end;
end;

begin
    readln(n);
    for i:=1 to n do
    begin
        inc(point);
        read(data[point]);
        if not flag[data[point]] then flag[data[point]]:=true else
            dec(point);
    end;
    n:=point;
    readln(a,b);
    ans:=(b div 8)-((a-1) div 8);
    for dis:=1 to n do
        Dfs(1,1,dis);
    writeln(ans);
end.

一不做二不休，把代码改成纯函数式的，从宏观层面毫无副作用。。
我是函数式编程的脑残粉。。
```c++
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

inline LL gcd(LL a, LL b)
{
return b == 0 ? a : gcd(b, a%b);
}

inline LL lcm(LL a, LL b)
{
return a/gcd(a, b)*b;
}

inline LL num(LL a, LL b, LL c)
{
return a%c?b/c-a/c:b/c-a/c+1;
}

inline LL two_num(LL a, LL b, LL c, LL d)
{
return max(0ll, num(a, b, c) - num(a, b, lcm(c,d)));
}

LL dfs(LL li[], LL i, LL n, LL m, LL get, LL a, LL b)
{
if (i == n && m == 0)
return two_num(a, b, 8, get);
if (i == n || m < 0)
return 0;
return dfs(li, i+1, n, m, get, a, b) + dfs(li, i+1, n, m-1, lcm(get, li[i]), a, b);
}

LL list_num(int i, int k, LL a, LL b, LL c[], LL n)
{
if (i == n+1)
return 0;
return k*dfs(c, 0, n, i, 1, a, b) + list_num(i+1, -k, a, b, c, n);
}

void read(LL a[], LL i)
{
if (i == -1)
return;
read(a, i-1);
cin >> a[i];
}

int main()
{
LL n, a[20], x, y;
cin >> n;
read(a, n-1);
cin >> x >> y;
cout << list_num(1, 1, x, y, a, n) << endl;
return 0;
}
```

#include <stdio.h>
#include <algorithm>
#define ll long long
using namespace std;
int sum=0,n,l;
ll f[16],st,ed;
ll gcd (ll a,ll b)
{if (a%b==0) {return b;}
return gcd(b,a%b);
}
ll z (ll a,ll b)
{if (a<b) {ll t=a;a=b;b=t;}
return a*b/gcd(a,b);
}
void zh (int re,int pl,ll ng)
{if (re==0)
{int k=(ed-st+1)/ng;
if ((ed%ng)<((st-1)%ng)) {k++;}
sum+=k*l;
return;
}
if (ng>ed) {return;}
if (pl>n) {return;}
int i;
for (i=pl;i<=n;i++)
{zh(re-1,i+1,z(ng,f[i]));}
return;
}
int main (){
int i;
scanf ("%d",&n);
for (i=1;i<=n;i++)
{scanf ("%I64d",&f[i]);}
sort (f+1,f+n+1);
scanf ("%I64d%I64d",&st,&ed);
sum=(ed-st+1)/8;
if (ed%8<(st-1)%8) {sum++;}
l=-1;
for (i=1;i<=n;i++)
{zh(i,1,8);l*=(-1);}
printf ("%d\n",sum);
return 0;
}

个人觉得代码写的还算清晰明了=_=

##
#include<iostream>
using namespace std;

typedef long long LL;
LL n,L,R,A[20];

inline LL gcd(LL a,LL b) {
if(!b) return a;
return gcd(b,a%b);
}
inline LL lcm(LL a,LL b) {
return a*b/gcd(a,b);
}

int main() {
cin>>n;
for(int i=0;i<n;i++) cin>>A[i];
cin>>L>>R;
LL ans=R/8-(L-1)/8;
for(int s=1;s<=(1<<n)-1;s++)
{
LL _lcm=8,cnt=0;
for(int i=0;i<n;i++) if(s&(1<<i)) _lcm=lcm(_lcm,A[i]) , cnt++;
if(cnt&1) ans -= R/_lcm-(L-1)/_lcm;
else ans += R/_lcm-(L-1)/_lcm;;
}
cout<<ans;
return 0;
}

记录信息
评测状态 Accepted
题目 P1629 八
递交时间 2015-07-31 15:55:29
代码语言 C++
评测机 VijosEx
消耗时间 2138 ms
消耗内存 509332 KiB
评测时间 2015-07-31 15:55:34
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 509332 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 509332 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 509332 KiB, score = 10
测试数据 #3: Accepted, time = 234 ms, mem = 509332 KiB, score = 10
测试数据 #4: Accepted, time = 125 ms, mem = 509332 KiB, score = 10
测试数据 #5: Accepted, time = 281 ms, mem = 509332 KiB, score = 10
测试数据 #6: Accepted, time = 359 ms, mem = 509332 KiB, score = 10
测试数据 #7: Accepted, time = 343 ms, mem = 509332 KiB, score = 10
测试数据 #8: Accepted, time = 531 ms, mem = 509332 KiB, score = 10
测试数据 #9: Accepted, time = 265 ms, mem = 509328 KiB, score = 10
Accepted, time = 2138 ms, mem = 509332 KiB, score = 100
代码
#include <iostream>
#include <stdio.h>
#include <algorithm>
using namespace std;
int dive[200];
int num[130000050];
int main()
{
int n,ans=0;
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
scanf("%d",&dive[i]);
for(int j=1;j<=3;j++)
{
if(dive[i]%2==0)dive[i]/=2;
else break;
}
}
sort(dive+1,dive+n+1);
int a,b;
scanf("%d%d",&a,&b);
a=(a+7)/8;b/=8;
for(int i=1;i<=n;i++)
{
int now=a/dive[i];
if(now%dive[i]!=0)now++;
for(int j=now;j*dive[i]<=b;j++)
num[j*dive[i]]=1;
}
for(int i=a;i<=b;i++)
if(!num[i])ans++;
printf("%d",ans);
}

P1629八
Accepted

记录信息

评测状态 Accepted
题目 P1629 八
递交时间 2014-11-03 20:10:16
代码语言 C++
评测机 上海红茶馆
消耗时间 995 ms
消耗内存 122872 KiB
评测时间 2014-11-03 20:10:18

评测结果

编译成功

测试数据 #0: Accepted, time = 93 ms, mem = 122872 KiB, score = 10

测试数据 #1: Accepted, time = 78 ms, mem = 122872 KiB, score = 10

测试数据 #2: Accepted, time = 78 ms, mem = 122868 KiB, score = 10

测试数据 #3: Accepted, time = 93 ms, mem = 122872 KiB, score = 10

测试数据 #4: Accepted, time = 93 ms, mem = 122872 KiB, score = 10

测试数据 #5: Accepted, time = 93 ms, mem = 122872 KiB, score = 10

测试数据 #6: Accepted, time = 125 ms, mem = 122868 KiB, score = 10

测试数据 #7: Accepted, time = 109 ms, mem = 122872 KiB, score = 10

测试数据 #8: Accepted, time = 140 ms, mem = 122864 KiB, score = 10

测试数据 #9: Accepted, time = 93 ms, mem = 122864 KiB, score = 10

Accepted, time = 995 ms, mem = 122872 KiB, score = 100

代码

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>

using namespace std;

bool x[125000000 + 10];
int y[15 + 2];
int i , j;
int a , b;
int n;
long long k , l;
long long sum;

int main()
{
while( scanf( "%d" , &n ) != EOF )
{
sum = 0;
memset( x , 1 , sizeof( x ) );
memset( y , 0 , sizeof( y ) );
for( i = 0 ; i < n ; i++ )
scanf( "%d" , &y[i] );
scanf( "%d %d" , &a , &b );
if( a % 8 == 0 )
a /= 8;
else
a = a / 8 + 1;
b /= 8;
for( i = 0 ; i < n ; i++ )
{
if( y[i] % 8 == 0 )
y[i] /= 8;
else
while( y[i] % 2 == 0 )
y[i] /= 2;
k = y[i];
if( a % k == 0 )
l = a;
else
l = ( a / k + 1 ) * k;
for( j = l ; j <= b ; j += k )
if( x[j] )
{
x[j] = 0;
sum++;
}
}
cout << b - a + 1 - sum << endl;
}
return 0;
}

非容斥AC

#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>

using namespace std;

bool x[1000000000 + 10];
int y[15 + 2];
int i , j;
int a , b;
int n;
long long sum;

int main()
{
while( cin >> n )
{
sum = 0;
memset( y , 0 , sizeof( y ) );
for( i = 0 ; i < n ; i++ )
scanf( "%d" , &y[i] );

scanf( "%d %d" , &a , &b );
for( i = 0 ; i < n ; i++ )
{
if( a % y[i] == 0 )
j = a / y[i];
else
j = ( ( a / y[i] ) + 1 ) * y[i];
for( ; j <= b ; j += y[i] )
x[j] = 1;
}
if( a % 8 == 0 )
i = a / 8;
else
i = ( ( a / 8 ) + 1 ) * 8;
for( ; i <= b ; i += 8 )
if( x[i] == 0 )
sum++;
cout << sum << endl;
memset( x , 0 , sizeof( x ) );
}
return 0;
}

program p1629;
var a:array[1..15] of int64;
p1,p2,sum:int64;
i,n:longint;
//
function make(p:int64):int64;
begin
make:=(p2 div p)-(p1 div p);
end;
//
function gcd(p,l:int64):int64;
begin
if l=0 then exit(p)
else gcd:=gcd(l,p mod l);
end;
//
procedure dfs(i,k,l:longint;p:int64);
var j:longint;
f:int64;
begin
if i=k then
begin
if k mod 2=0 then sum:=sum+make(p)
else sum:=sum-make(p);
exit;
end;
if l+(i-k)>n then exit;
for j:=l+1 to n do
begin
f:=a[j]*p div gcd(a[j],p);
dfs(i,k+1,j,f);
end;
end;
//
begin
readln(n);
for i:=1 to n do read(a[i]);readln;
read(p1,p2);
sum:=make(8);
for i:=1 to n do dfs(i,0,0,8);
write(sum);
end.

#include

#include

#include

__int64 n,left,right;

__int64 num[20];

__int64 a[20],b[20],p;//a数组，保存每个和8最小公倍数值 b数组保存选取情况，p保存有的数量 1取，0不取

__int64 ans,fuck;

__int64 xx[20];//保存计算的东东

__int64 gcd(__int64 a,__int64 b){

if (b == 0) return a;

return gcd( b , a % b );

}

void print(){

int i;

for ( i = 1 ; i right) return;

}

c = right / temp - ( left - 1 ) / temp;

if (fuck % 2 == 0)

ans + = c;

else ans - = c;

}

void make(){

int i,c,temp;

fuck = 0;//目前读取到0个数字

for (i = 1 ; i < = p ; i ++) if (b[i] == 1) fuck++; //看看有几个数字

if (fuck == 0) return ;

// print();

for (i = 1 ; i < = p ; i ++)

if (b[i] == 1) get(i);//第i个数字，作为和8的最小公倍数

}

void dfs(int k){

int i,j;

// printf("%d ",k);

if (k == p) { make(); return;} //满足条件时候，进行最后处理

b[k+1] = 1;

dfs(k + 1);

b[k+1] = 0;

dfs(k + 1);

}

void init(){

int i;

p=0;

ans=0;

memset(num,0,sizeof(num));

memset(a,0,sizeof(a));

memset(b,0,sizeof(b));

scanf("%d",&n);//有n个数字

for (i = 1 ; i < = n ; i ++) scanf("%d",&num[i]); //读入这n个数字

scanf("%d%d",&left,&right); //读入左边和右边的边界条件

for (i = 1 ; i < = n ; i ++){ //判断，并且构造每个数字和8的最小公倍数

if (num[i] ==1 || num[i] ==2 || num[i] ==4 || num[i] ==8 ){

// printf("0\n");

return ;

}

a[++p]= ( num[i] * 8 ) / gcd( num[i] , 8 );

}

// printf("%d!",p);

ans=right / 8 - ( left - 1 ) / 8;//初始化

dfs(0);

printf("%I64d\n",ans);

}

int main(){

//---|main---|-

init();

system("pause");

return 0;

}

只过3个点，哪个大牛帮忙看下……

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

一开始想多了.....

有没有不用 斥容 的

得 高分的？？

囧~

通过 　　250人

容斥...

跳格被无情的吃了，晕……

#include

#include

#include

#define maxn 16

long N,a,b,A[maxn],sign=-1,Ans;

void swap(long long *a,long long *b){

long long tmp=*a;*a=*b;*b=tmp;

}

long long gcd(long long a,long long b){

if (!b) return a;

if (a

...

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

。。。。莫名其妙的30分。。。。

我的上午就这么没了..=.=

为什么！！！！！！！

为什么设置long long的时候I64不行、 lld却可以啊！！！！！！！！

Flag 　　 Accepted

题号 　　P1629

类型(?) 　　数论 / 数值

通过 　　200人

提交 　　863次

通过率 　　23%

难度 　　1

紧跟楼下的。。

8月30日我做了一下这题。。只过了3个点。。

现在终于不一样了