首页 > 其他 > 详细

一本通 P1801 异或

时间:2019-11-24 20:10:37      阅读:111      评论:0      收藏:0      [点我收藏+]

一本通原题

因为\(?? = ??\)时肯定无解,我们不妨设\(?? > ??\)
那么有\(gcd(a,b)\leq a-b\), \(a\ xor\ b\geq a-b\),很明显有\(?? = ?? ? ??\)
我们依然 枚举\(c\), \(a=i*c\),因为\(gcd(a,a-c)=c\)
所以我们只需判断\(a\ xor\ c=a-c\)即 可,时间\(O(n\ log_2n)\),因为常数小,所以可以过。

#include<cstdio>
#define re register
using namespace std;
template<typename T>
inline void read(T&x)
{
    x=0;
    char s=getchar();
    bool f=false;
    while(!(s>='0'&&s<='9'))
    {
        if(s=='-')
            f=true;
        s=getchar();
    }
    while(s>='0'&&s<='9')
    {
        x=(x<<1)+(x<<3)+s-'0';
        s=getchar();
    }
    if(f)
        x=(~x)+1;
    return;
}
int ans,n;
int main()
{
    read(n);
    for(re int i=1; i<=n; i++)
        for(re int j=i<<1; j<=n; j+=i)
            ans+=(i^j)==j-i;
    printf("%d\n",ans);
    return 0;
}

一本通 P1801 异或

原文:https://www.cnblogs.com/wangjunrui/p/11923540.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!