汕头企业网站建设服务,环境艺术设计网站推荐,抚州教育网站建设,网络推广培训视频异或
jzoj 2298
题目大意#xff1a;
定义nbnbnb数对a,ba,ba,b为gcd(a,b)abgcd(a,b)a^bgcd(a,b)ab的数对#xff0c;问不大于nnn的nbnbnb数对有多少对
输入样例#1
12输出样例#1
8输入样例#2
123456输出样例#2
214394数据范围
测试点数据规模11021003100045000510000…异或
jzoj 2298
题目大意
定义nbnbnb数对a,ba,ba,b为gcd(a,b)abgcd(a,b)a^bgcd(a,b)ab的数对问不大于nnn的nbnbnb数对有多少对
输入样例#1
12输出样例#1
8输入样例#2
123456输出样例#2
214394数据范围
测试点数据规模110210031000450005100006100000750000081000000950000001020000000
解题思路
我们第一个想到的就是暴力枚举每一个数对然后判断时间复杂度o(n2logn)o(n^2log_n)o(n2logn)会TLE 因为axorbca\ xor\ bca xor bc则axorcba\ xor\ cba xor cb所以我们可以枚举c然后在枚举a是c的几倍然后用公式求出b然后再求gcd判断是否和c一样时间复杂度o(n(logn)2)o(n(log_n)^2)o(n(logn)2),也会TLE 我们可以经过证明得知ba-c 证明 首先a−b⩽axorba-b\leqslant a\ xor\ ba−b⩽a xor b 我们距离两个二进制数 101101011010110 110001100011000 他们相减是222 xorxorxor是14 我们可以发现xorxorxor是不同位的和 而相减是加某些不同位再减某些不同位最大就是所有不同位加也不大于xorxorxor 所以a−b⩽axorba-b\leqslant a\ xor\ ba−b⩽a xor b 然后我们可以发现a−b⩽ca-b\leqslant ca−b⩽c 我们也列两个例子: a12a12a12 b9b9b9 c3c3c3 我们设asa/c4asa/c4asa/c4 bsb/c3bsb/c3bsb/c3 因为a,b都是c的倍数所以a−bas∗c−bs∗c(as−bs)∗ca-bas*c-bs*c(as-bs)*ca−bas∗c−bs∗c(as−bs)∗c 因为aaa不等于bbb 所以as−bs⩾1as-bs\geqslant 1as−bs⩾1 所以(as−bs)∗c⩾c(as-bs)*c\geqslant c(as−bs)∗c⩾c 所以a−b⩾ca-b\geqslant ca−b⩾c 假设存在ca−bca-bca−b 则ca−b⩽axorbca-b\leqslant a\ xor\ bca−b⩽a xor b 不满足caxorbca\ xor\ bca xor b 所以ca−bca-bca−b 所以ba−cba-cba−c 因此gcda,bgcd(a,a−c)cgcda,bgcd(a,a-c)cgcda,bgcd(a,a−c)c 所以我们只需判断是否有caxorbca\ xor \ bca xor b即可
代码
#includecstdio
using namespace std;
int n,a,b,ans;
int main()
{scanf(%d,n);for (int i1;i(n1);i)for (int j2;i*jn;j){ai*j;//求出aba-i;//相减得到bif (i(a^b))//判断c是否等于a^bans;}printf(%d,ans);
}
