多校联赛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
####离散化