数论小常识

//UVA  12716


#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <utility>
#include <vector>
#include <map>
#include <queue>
#include <stack>
#include <cstdlib>
#include <cmath>
typedef long long ll;
#define lowbit(x) (x&(-x))
#define ls l,m,rt<<1
#define rs m+1,r,rt<<1|1
using namespace std;
#define pi acos(-1)
#define P pair<ll,ll>
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
",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 个整数，表示

输出描述:

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

示例1

输入

复制

3
1 2 3

输出

复制

说明

我们

备注:

对于所有的数据，保证

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

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <string>
 5 #include <algorithm>
 6 #include <utility>
 7 #include <vector>
 8 #include <map>
 9 #include <queue>
10 #include <stack>
11 #include <cstdlib>
12 #include <cmath>
13 typedef long long ll;
14 #define lowbit(x) (x&(-x))
15 #define ls l,m,rt<<1
16 #define rs m+1,r,rt<<1|1
17 using namespace std;
18 #define pi acos(-1)
19 #define P pair<ll,ll>
20 const ll mod = 100000007;
21 int n;
22 /*
23 由于a^b>=a-b,那么可以令某个区间的数异或和为a,累加和为b
24 现在考虑，是否需要加入c？
25 a^c+b+c>=a-c+b+c==a+b
26 因此，加入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<n;i++)
34     {
35         scanf("%lld",&x);
36         sum1=(sum1^x)%mod;
37         sum2=(sum2+x)%mod;
38     }
39     printf("%lld
",(sum1+sum2)%mod);
40     return 0;
41 }