#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

1 10

Sample Output

HINT

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

题意

题解：

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

代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            
             #include 
             
              #include 
              
               #include 
               
                #include 
                
                 #include 
                 #include 
                  
                   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-9const 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<
                   
                    <