首页 > 代码库 > 洛谷 U4704 函数

洛谷 U4704 函数

设gcd(a,b)为a和b的最大公约数,xor(a,b)为a异或b的结果。

题目描述

kkk总是把gcd写成xor。今天数学考试恰好出到了gcd(a,b)=?这样的题目,但是kkk全部理解成了xor(a,b)=?

幸好这是填空题,老师只看kkk的答案是否正确而不在意过程。于是kkk想知道,对于所有不超过N的正整数a和b(a>=b)有多少组(a,b)满足可以使kkk的答案是正确的?

输入输出格式

输入格式:

 

一个整数N

 

输出格式:

 

输出(a,b)的组数

 

输入输出样例

输入样例#1:
7
输出样例#1:
4

说明

1<=N<=100000

分析:直接n2必然超时;

   由a-b<=xor(a,b)=gcd(a,b)即可枚举最大公因子;

代码:

#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <climits>#include <cstring>#include <string>#include <set>#include <map>#include <queue>#include <stack>#include <vector>#include <list>#define rep(i,m,n) for(i=m;i<=n;i++)#define rsp(it,s) for(set<int>::iterator it=s.begin();it!=s.end();it++)#define mod 1000000007#define inf 0x3f3f3f3f#define vi vector<int>#define pb push_back#define mp make_pair#define fi first#define se second#define ll long long#define pi acos(-1.0)#define pii pair<int,int>#define Lson L, mid, rt<<1#define Rson mid+1, R, rt<<1|1const int maxn=5e2+10;using namespace std;ll gcd(ll p,ll q){return q==0?p:gcd(q,p%q);}ll qpow(ll p,ll q){ll f=1;while(q){if(q&1)f=f*p;p=p*p;q>>=1;}return f;}inline ll read(){    ll x=0;int f=1;char ch=getchar();    while(ch<0||ch>9){if(ch==-)f=-1;ch=getchar();}    while(ch>=0&&ch<=9){x=x*10+ch-0;ch=getchar();}    return x*f;}int n,m,k,t;ll ans;int main(){    int i,j;    scanf("%d",&n);    for(i=1;i<=n/2;i++)    {        for(j=2*i;j<=n;j+=i)            if(i==(j^(j-i)))ans++;    }    printf("%lld\n",ans);    //system("Pause");    return 0;}

洛谷 U4704 函数