多校联赛6补题

, ,
破天荒过了两题！

2019-08-07
###1TDL
####主要是两个细节，

a ^ b=c可以推出a ^ c=b
质数密度分布

按位异或的3个特点:
(1) 00=0,01=1 0异或任何数＝任何数
(2) 10=1,11=0 1异或任何数－任何数取反
(1^4)=5,(~4)=-5;
(3) 任何数异或自己＝把自己置0
按位异或的几个常见用途:
(1) 使某些特定的位翻转
例如对数10100001的第2位和第3位翻转，则可以将该数与00000110进行按位异或运算。
　　　　　 10100001^00000110 = 10100111

(2) 实现两个值的交换，而不必使用临时变量。
例如交换两个整数a=10100001，b=00000110的值，可通过下列语句实现：
　　　　a = a^b； 　　//a=10100111
　　　　b = b^a； 　　//b=10100001
　　　　a = a^b； 　　//a=00000110
移位运算是最有效的计算乘/除乘法的运算之一。

用一条语句判断一个整数是不是2的整数次方。
!（x & (x - 1)）
####标程：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include<cstdio>
typedef long long ll;
int Case, m, d;
ll k, ans;
ll gcd(ll a, ll b)
{
    return b ? gcd(b, a % b) : a;
}
inline ll cal(ll n, int m)
{
    if(n < 1)
        return 0;
    for(ll i = n + 1;; i++)
        if(gcd(n, i) == 1)
        {
            m--;
            if(!m)
                return i - n;
        }
}
int main()
{
    scanf("%d", &Case);
    while(Case--)
    {
        scanf("%lld%d", &k, &m);
        ans = -1;
        for(d = 1; d < 700; d++)
            if(cal(k ^ d, m) == d)
            {
                if(ans == -1)
                    ans = k ^ d;
                else if(ans > (k ^ d))
                    ans = k ^ d;
            }
        printf("%lld\n", ans);
    }
}

###2Snowy Smile
####离散化