首页 > 其他分享 >UVA12716 GCD等于XOR GCD XOR

UVA12716 GCD等于XOR GCD XOR

时间:2023-06-18 22:12:38浏览次数:59  
标签:UVA12716 XOR GCD int 枚举 等于

UVA12716 GCD等于XOR GCD XOR

一道数学题。

 首先,我们可以知道,a-b>=gcd(a,b)=c;

其次,a-b<=a xor b=c;

综上,可得a-b=c,即a-b=a xor b.

由于范围不大,直接枚举。

第一层枚举c(因为c较少),第二层枚举a,(b=a-c)  再判断c是否等于a^b即可。

#include<bits/stdc++.h>
using namespace std;
const int N=3e7+7;
int n,ans[N];
int main(){
    for(int c=1;c<=(N>>1);c++){
        for(int a=c<<1,b;a<=N;a+=c){
            b=a-c;
            if((a^b)==c) ans[a]++;
        }
    }
    for(int i=1;i<=N;i++){
        ans[i]+=ans[i-1];
    }
    int T,cnt=0;
    cin>>T;
    while(T--){
        cin>>n;
        cout<<"Case "<<++cnt<<": "<<ans[n]<<endl;
    }
    return 0;
}

 

标签:UVA12716,XOR,GCD,int,枚举,等于
From: https://www.cnblogs.com/DongPD/p/17489865.html

相关文章

  • [数论]Divisor and Gcd
    DivisorandGcd1、算术基本定理:n的质因数分解唯一一些常见结论:1.素数无限2.\(\lim_{n\rightarrow+\infty}n\prod\dfrac{n}{\frac{n}{\ln{n}}}\)(Π(n)表示<=n素数的个数)————即n以下素数个数大约是\(\frac{n}{\ln(n)}\)级别的3.\(Pn=O(nlogn)\)级别的(Pn表示素数)......
  • [ABC162E] Sum of gcd of Tuples (Hard)
    题面翻译给定\(n,k\),求\[\sum^k_{a_1=1}\sum^k_{a_2=1}\sum^k_{a_3=1}\dots\sum^k_{a_n=1}gcd(a_1,a_2,a_3,\dots,a_n)\mod\1000000007\]制約$2\\leq\N\\leq\10^5$$1\\leq\K\\leq\10^5$。思路点拨我们看到这么多\(\gcd\)的式子,我们自然想到莫比乌斯反演......
  • AtCoder Beginner Contest 249 G Xor Cards
    洛谷传送门AtCoder传送门好题。套路地,考虑枚举最优解的\(a\)异或和二进制下与\(k\)的\(\text{LCP}\),设在第\(i\)位不同。这样的好处是\(i\)之后的位可以随便选。之后按位贪心确定最优解\(b\)的异或和。考虑之前的答案是\(res\),当前在确定第\(j\)位,如何判断\(r......
  • AtCoder Beginner Contest 223 H Xor Query
    洛谷传送门AtCoder传送门考虑一个无脑做法:线段树维护区间线性基。时间复杂度是\(O(m\logn\log^2V)\),过于优秀以至于无法接受。事实上我们并不需要维护区间线性基,因为不带修。考虑“可持久化线性基”,开\(n\)个线性基,第\(i\)个维护前缀\([1,i]\)的数。并且插入线性......
  • The XOR Largest Pair
    #include<iostream>#include<cstdio>#include<cmath>#include<algorithm>#include<cstring>usingnamespacestd;intbit[32];intn,num[5211314];structTrie{ inttrie[5211314][2],tot=1; inlinevoidInsert(inta){ ......
  • [数论]GCD&LCM&欧拉函——推柿子+例题
    GCD&LCM&欧拉函——推柿子一、\(\sum_{i=1}^{n}[\gcd(i,n)=d]\)\(\sum_{i=1}^{n}[\gcd(i,n)=d]\)\(=\sum_{i=1}^{\frac{n}{d}}[\gcd(i,\frac{n}{d})=1]\)\(=\phi(\frac{n}{d})\)二、\(\sum_{i=1}^{n}\gcd(i,n)\)\(\sum_{i=1}^{n}\gcd(i,......
  • Educational Codeforces Round 20-C. Maximal GCD
    原题链接C.MaximalGCDtimelimitpertestmemorylimitpertestinputoutputn.Youshouldcreatesuch strictlyincreasing sequenceof k positivenumbers a1, a2, ..., ak,thattheirsumisequalto nGr......
  • Xor-MST
    Xor-MST这道题其实是一种最小生成树算法名曰Boruvka的算法,但是平时还是Kruskal算法用的说,相信大家也是由它想起的。根据套路,由于要求的是异或边权之和的最小值,果断构建01trie。我们将样例画出来我们可以对这颗树进行dfs,可以看出两个点的LCA越深,那么它们合并代价就越......
  • [ABC201E] Xor Distances 题解
    XorDistances题目大意给定一颗带边权无根树,定义\(\text{dis}(i,j)\)表示\(i,j\)两点在树上的最短路径的边权的异或和。求:\[\sum_{i=1}^n\sum_{j=i+1}^n\text{dis}(i,j)\]思路分析首先,容易证明:\[\text{dis}(i,j)=\text{dis}(i,x)\oplus\text{dis}(x,j)\]这个式子告诉我......
  • 实现免杀:Shellcode的AES和XOR加密策略(vt查杀率:4/70)
    前言什么是私钥和公钥私钥和公钥是密码学中用于实现加密、解密和数字签名等功能的关键组件。私钥是一种加密算法中的秘密密钥,只有密钥的拥有者可以访问和使用它。私钥通常用于数字签名和数据加密等场景中,它可以用于对数据进行加密,同时也可以用于解密已经被加密的数据。公钥是......