hihocoder〓〓1178:暴力を計数します.

ヽoo.ツ
Time Limit:20 Sec
メモリLimit:256 MB
タイトル接続
http://hihocoder.com/problemset/problem/1178
Description
Rowdarkは邪悪な魔法使いです.彼は大きな呪術師Lichの伝記を読んでいると、古代生物、魚丸を召喚する黒の魔法の類を発見しました.
魔法nは、タイプiの魚丸を召喚することができます.また、iだけがx x or n*xと表示されます.ある正の整数xと固定のnです.
Rowdarkが知りたいのですが、タイプは[L,R]の間の魚丸はどれぐらいの種類が魔法nに召喚されますか?
Input
最初の行を入力すると、整数n(1≦n≦107)が含まれます.2行目は2つの整数、L、R(0≦L≦R≦107)を含む.
Output
行の整数は答えを表します.
 
Sample Input
2
1 10
Sample Output
3
HINT
 3(1 x or 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=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
//**************************************************************************************

int a[10000010];
int main()
{
    int n=read();
    int l=read(),r=read();
    for(int i=1;i<=100000000;i++)
    {
        ll tmp=(ll)(i)^(1LL*i*n);
        if(tmp>r||tmp<0)
            continue;
        a[tmp]=1;
    }
    int ans=0;
    for(int i=l;i<=r;i++)
        if(a[i]==1)
            ans++;
    cout<<ans<<endl;
}