| by XianKa | No comments

【数论】CF1110C

http://codeforces.com/problemset/problem/1110/C

题意是给一个a让求一个0<b<a使得gcd(a ^ b , a & b) 要最大

  • 首先注意到a^b和a&b的每一位都是相反的,所以说很容易想到构造一个b使得b&a=0,这样答案就是a^b。构造方法就是把a的每一位1变成0,0变成1。
  • 对于a的每一位全是1的情况需要单独讨论。
  • 如果a的每一位都是1,任取一个b,可以得到a^b=a-b , a&b=b 这个结论。那么问题就变成了求gcd(a-b,b),也就是gcd(a,b)_max。
  • 对于求最大的gcd,把a分解质因数,除掉其中一个最小的质因子,就是答案。
  • 由于本题时间不紧,而且cf测评机都是香港记者,所以可以直接根号复杂度暴力分解。当然也可以预处理质数表
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int q,a;
int main()
{
    scanf("%d",&q);
    while(q--)
    {
        scanf("%d",&a);
        //a=q;
        int res=0;
        for(int i=0;(1<<i)+res < a;i++)
        {
            if(!((1<<i)&a) ) 
                res+=(1<<i); 
            //cout<<res<<'-';
        }
        if(res) printf("%d\n",res^a);
        else
        {
            bool flag=true;
            for(int i=2;i*i<=a;i++) 
            {
                if(a%i==0)
                {
                    flag=false;
                    printf("%d\n",a/i);
                    break;
                }
            }
            if(flag) printf("1\n");
        }
    }
}

发表评论