数论小常识

阅读量：5315 次

发布时间：2019-06-14

本文共 2083 字，大约阅读时间需要 6 分钟。

//UVA  12716#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          #include 
          
           #include 
           
            #include 
            #include 
             
              #include 
              
               #include 
               
                #include 
                
                 typedef long long ll;#define lowbit(x) (x&(-x))#define ls l,m,rt<<1#define rs m+1,r,rt<<1|1using namespace std;#define pi acos(-1)#define P pair
                 
                  const int N = 3e7;ll ans[N+10];void init(){ for(int i =1;i<=N/2;i++) { for(int j =i*2;j<=N;j+=i){ int k=j-i; if((j^k)==i) ans[j]++; } } for(int i =2;i<=N;i++){ ans[i]+=ans[i-1]; }}int n,t;int main(){ init(); scanf("%d",&t); for(int i=1;i<=t;i++){ scanf("%d",&n); printf("Case %d: %d\n",i,ans[n]);}return 0;}

题意：输入整数n（1<=n<=3千万），有多少对整数（a，b）满足：1<=b<=a<=n，且gcd（a，b）=a XOR b。例如：n=7时，有4对：（3，2），(5,4），(6,4），(7,6）。题解：gcd(a,b)==a^b令gcd(a,b)=c,由于a^b>=a-b(a>=b), 那么c>=a-b  (1) a=k1c,b=k2c(k1>=k2),那么a-b=(k1-k2)c>=c     (2) 由(1)和(2)可得a-b==c,也就是a^b==a-b可以枚举c(a的因数).

牛客练习赛42 B

题目描述

注意本题有模数

给定一个长度为 n 的序列 { a } ，求：

其中

输入描述:

第一行一个整数 n 。 第二行 n 个整数，表示 aiai 。

输出描述:

一行一个整数 ans ，表示答案。

示例1

输入

31 2 3

输出

说明

我们 显然需要将所有的数字都选上显然需要将所有的数字都选上，此时 ans=(1⊕2⊕3)+1+2+3=6ans=(1⊕2⊕3)+1+2+3=6 。

备注:

对于所有的数据，保证

样例：想不到吧，你的做法至少能过样例！

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 #include 
          
            5 #include 
           
             6 #include 
            
              7 #include 
             
               8 #include 
               9 #include 
               
                10 #include 
                
                 11 #include 
                 
                  12 #include 
                  
                   13 typedef long long ll;14 #define lowbit(x) (x&(-x))15 #define ls l,m,rt<<116 #define rs m+1,r,rt<<1|117 using namespace std;18 #define pi acos(-1)19 #define P pair
                   
                    20 const ll mod = 100000007;21 int n;22 /*23 由于a^b>=a-b,那么可以令某个区间的数异或和为a,累加和为b24 现在考虑，是否需要加入c？25 a^c+b+c>=a-c+b+c==a+b26 因此，加入c会令原来的结果不变或者变大，因此要取所有的数。 27 */28 int main()29 {30 scanf("%d",&n);31 ll x;32 ll sum1=0,sum2=0;33 for(int i=0;i