做网站的技术困难,常州新北区建设局网站,大学网站建设管理办法信息化,北京住房与建设部网站异或
题目大意
问你不小于nnn的数对(a,b)(a,b)(a,b)#xff0c;有多少个满足gcd(a,b)a⊕bgcd(a,b)a \oplus bgcd(a,b)a⊕b
输入样例#1
12输出样例#1
8输入样例#2
123456输出样例#2
214394数据范围
测试点数据规模110210031000450005100006100000750000081000000950000…异或
题目大意
问你不小于nnn的数对(a,b)(a,b)(a,b)有多少个满足gcd(a,b)a⊕bgcd(a,b)a \oplus bgcd(a,b)a⊕b
输入样例#1
12输出样例#1
8输入样例#2
123456输出样例#2
214394数据范围
测试点数据规模110210031000450005100006100000750000081000000950000001020000000
解题思路
我们设cgcd(a,b)cgcd(a,b)cgcd(a,b) 我们可以枚举ccc 然后枚举aaa是ccc的多少倍 由此得出a,ca,ca,c 我们可以通过gcdgcdgcd求出bbb然后判断是否满足a⊕bca \oplus bca⊕bc 但是这个时间复杂度过大我们要进行优化 我们先证明a−b⩽a⊕ba-b \leqslant a \oplus ba−b⩽a⊕b 我们观察以下两个字符串xyxyxy x:x:x: 11001 y:y:y: 00101 xor:xor:xor: 11100 1...对于x,yx,yx,y都是1的位xorxorxor和−-−得出结果都是0
2...对于只有yyy是1的位 因为ababab所以在更高的位肯定有只有xxx是1的位这样减出来的结果才可能是正数 因此−-−得出的结果是更高一位只有xxx是1的位减这一位 而xorxorxor得出的是这两位的和
3...对于只有xxx是1且无需用去减的位xorxorxor和−-−得出结果都是1 综上所述a−b⩽a⊕ba-b \leqslant a \oplus ba−b⩽a⊕b 现在我们来证明c⩽a−bc \leqslant a-bc⩽a−b 因为cgcd(a,b)cgcd(a,b)cgcd(a,b) 我们设 ac∗asac*asac∗as bc∗bsbc*bsbc∗bs
若ababab则 gcd(a,b)1gcd(a,b)1gcd(a,b)1 a⊕b0a \oplus b0a⊕b0 gcd(a,b)≠a⊕bgcd(a,b) \neq a \oplus bgcd(a,b)a⊕b ∴a≠b\therefore a \neq b∴ab
∵a≠b且a⩾b\because a \neq b 且a \geqslant b∵ab且a⩾b aba bab ∵asbs\because as bs∵asbs as−bs⩾1as - bs\geqslant 1as−bs⩾1 (as−bs)×c⩾c(as - bs)\times c \geqslant c(as−bs)×c⩾c a−b⩾ca-b\geqslant ca−b⩾c 若a−b≠ca-b\neq ca−bc 则ca−b⩽a⊕bc a-b \leqslant a \oplus bca−b⩽a⊕b ca⊕bca \oplus bca⊕b 无法满足ca⊕bca \oplus bca⊕b ∴a−bc\therefore a-bc∴a−bc 这样我们通过ba−cba-cba−c求出bbb 然后判断ccc是否等于a⊕ba \oplus ba⊕b即可
代码
#includecstdio
#includecstring
#includeiostream
#includealgorithm
#define ll long long
using namespace std;
int n, a, b, ans;
int main()
{scanf(%d, n);for (int i 1; i n / 2; i)for (int j 2; i * j n; j){a i * j;b a - i;//求bif (i (a^b)) ans;}printf(%d, ans);return 0;
}
