2298. 【noip普及组2T4】异或
(File IO): input:gcdxor.in output:gcdxor.out
真~思路(不严谨的思考):
我们用原方案是不可以的,毫无疑问是这个数据太坑爹了!!!最郁闷的还是这个数据解释是假的,假的,假的!!!
经过一番痛苦的思考(快乐的偷窥)我们可以得出gcd(a,b)是一定小于等于abs(a-b)的。证明:易得证【滑稽】毫无疑问,我们知道a+b大于等于1;不妨设系数k,则有ak+bk大于等于k;将其转换可以得出gcd(a,b)<=abs(a-b)接下了我们确定abs(a-b)的上限,结合题意很容易猜出是i亦或j。证明:将两个东西转换成二进制。两者大多相同,但当0在上1在下时,相减会退位而亦或会想加。
真~CODE:
#include<iostream> #include<cstdio> #include<cmath> using namespace std; int n,ans=0; int main() { cin>>n; for(int i=1;i<=n;i++) { for(int j=2*i;j<=n;j+=i) { if(j-i==(i^j)) ans++; } } cout<<ans; }