hihocoder #1178 : 计数 暴力

#1178 : 计数

Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://hihocoder.com/problemset/problem/1178

Description

Rowdark是一个邪恶的魔法师。在他阅读大巫术师Lich的传记时，他发现一类黑魔法来召唤远古生物，鱼丸。

魔法n能召唤类型i鱼丸当且仅当i能够被表示为x xor n*x对于某个正整数x和固定的n。

Rowdark想知道类型为[L,R]之间的鱼丸有多少种能被魔法n召唤。

Input

输入第一行包含个整数n(1 ≤ n ≤ 107)。

第二行包含两个整数，L, R(0 ≤ L ≤ R ≤ 107)。

Output

一行一个整数表示答案。

Sample Input

2

1 10

Sample Output

3

HINT

只有3(1 xor 2), 5(3 xor 6), 6(2 xor 4), 9(7 xor 14), 10(6 xor 12)满足要求。

题意

题解：

正着想不会，那我们就逆着想就好了~

代码：

#include <cstdio>

#include <cmath>

#include <cstring>

#include <ctime>

#include <iostream>

#include <algorithm>

#include <set>

#include <vector>

#include <sstream>

#include <queue>

#include <typeinfo>

#include <fstream>

#include <map>

#include <stack>

typedef long long ll;

using namespace std;

//freopen("D.in","r",stdin);

//freopen("D.out","w",stdout);

#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)

#define test freopen("test.txt","r",stdin)

#define maxn 100001

#define mod 10007

#define eps 1e-9

const int inf=0x3f3f3f3f;

const ll infll = 0x3f3f3f3f3f3f3f3fLL;

inline ll read()

{

    ll x=,f=;char ch=getchar();

    while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

    while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

//**************************************************************************************

int a[];

int main()

{

    int n=read();

    int l=read(),r=read();

    for(int i=;i<=;i++)

    {

        ll tmp=(ll)(i)^(1LL*i*n);

        if(tmp>r||tmp<)

            continue;

        a[tmp]=;

    }

    int ans=;

    for(int i=l;i<=r;i++)

        if(a[i]==)

            ans++;

    cout<<ans<<endl;

}