GCD XOR UVA - 12716 ——筛法建立约数表+xor运算+数学规律

短命女 2022-06-15 06:37 135阅读 0赞

Think:  
1埃式筛法思想建立约数表  
2初始打表寻找运算的数学规律  
3xor运算(不带进位的二进制加法)  
运算法则

1. a ⊕ a = 0
    2. a ⊕ b = b ⊕ a
    3. a ⊕b ⊕ c = a ⊕ (b ⊕ c) = (a ⊕ b) ⊕ c;
    4. d = a ⊕ b ⊕ c 可以推出 a = d ⊕ b ⊕ c.((a^b) == c <=> a(a^c) == b)
    5. a ⊕ b ⊕ a = b.
    6.若x是二进制数0101，y是二进制数1011；
    则x⊕y=1110
    只有在两个比较的位不同时其结果是1，否则结果为0
    即“两个输入相同时为0，不同则为1”！

[xor运算——百度百科链接][xor]

[vjudge题目链接][vjudge]

以下为Accepted代码

/*
    1打表发现数学规律gcd(a, b) == (a^b) => (a-b) == (a^b)
    2筛法思想建立约数表
    3xor运算:(a^b) = c <=> (a^c) = b;
    */
    #include <cstdio>
    #include <cstring>
    
    using namespace std;
    
    int v[30000004] = {
       0};
    
    int main(){
        int a, b, c;
        ///筛法思想建立约数表
        for(c = 1; c <= 15000000; c++){
            for(a = c + c; a <= 30000000; a += c){
                b = a - c;
                if(c == (a^b))
                    v[a]++;
            }
        }
        ///now:v[a]:(a, xi);
        for(int i = 2; i <= 30000000; i++){
            v[i] += v[i-1];
        }
        ///now:v[a]:(ai, xi);
        int T, k, n;
        scanf("%d", &T);
        for(k = 1; k <= T; k++){
            scanf("%d", &n);
            printf("Case %d: %d\n", k, v[n]);
        }
        return 0;
    }

[xor]: http://baike.baidu.com/link?url=zhH1IXXUBPsTpYEuScaVDKVCNvFRHhpA0-nEsMblIdX1-FPly6TOmoPQxusVMDgnj8cSsTF2ZK8QmixHjqZ2HbjzSmutshT7WiNMuHbpW__
[vjudge]: https://vjudge.net/problem/UVA-12716

发表评论取消回复

表情：

评论列表（有 0 条评论，135人围观）

还没有评论，来说两句吧...

相关阅读

相关【区间DP】XOR-pyramid

[Problem - B - Codeforces][] 题意： ![ce934eda659b30bf3e5794265e2f9c3f.png][] 思路：考虑区间D

布满荆棘的人生/ 2024年03月26日 20:42/ 0 赞/ 33 阅读

相关 ♥codeforces 627A-XOR Equation【数学】

A. XOR Equation time limit per test 2 seconds memory limit per test 256 megabytes i

痛定思痛。/ 2022年08月21日 04:26/ 0 赞/ 116 阅读

相关 GCD XOR UVA - 12716 ——筛法建立约数表+xor运算+数学规律

Think: 1埃式筛法思想建立约数表 2初始打表寻找运算的数学规律 3xor运算(不带进位的二进制加法) 运算法则 1. a ⊕ a = 0

短命女/ 2022年06月15日 06:37/ 0 赞/ 136 阅读

相关 Prime Gap UVA - 1644——筛法建素数表

Think: 1题意：输入一个整数n，输出后一个素数和前一个素数的差值，输入是素数时输出0，n不超过1299709（第100000个素数），输入0时结束不进行操作 2方

￡神魔★判官ぃ/ 2022年06月14日 04:39/ 0 赞/ 127 阅读

相关 UVa12716 - GCD XOR

输入一个整数，有多少对（a，b）满足1<=b<=a<=n，且 gcd（a，b） = a xor b gcd是最大公约数 xor 是异或运算，2进制 1001^10

谁践踏了优雅/ 2022年06月08日 10:10/ 0 赞/ 109 阅读

相关 xor

给出n个数字a\_1,…a\_n,问最多有多少个不重叠的非空区间，使得每个区间内数字的xor都等于0，即得出最大的k，使得存在k个区间（l\[i\],r\[i\]），满足1<=

绝地灬酷狼/ 2022年06月08日 08:42/ 0 赞/ 125 阅读

相关【进制转换＋异或运算】XOR Sorting HihoCoder - 1509

Think: 1知识点：【进制转换＋异或运算】 2题意：输入一个序列a\[1..n\]，判断满足一下两个条件的S有多少个 (1):0 <= S < pow(2, 6

迷南。/ 2022年05月31日 01:45/ 0 赞/ 117 阅读

相关 (打表找规律+前缀异或和)MORE XOR

题目链接：[https://nanti.jisuanke.com/t/38230][https_nanti.jisuanke.com_t_38230] 比赛的时候也在推规律，

待我称王封你为后i/ 2022年02月16日 14:02/ 0 赞/ 194 阅读

相关 BZOJ4269 再见xor

考前挣扎线性基裸题 mx直接求次大直接从低到高枚举第一个非0位然后次大就是异或上就行了【显然贪心呐qwq 不到800b可还行 //Love and Fr

ゝ一纸荒年。/ 2021年12月23日 06:19/ 0 赞/ 172 阅读

相关基于Tensorflow轻松实现XOR运算

对于“XOR”大家应该都不陌生，我们在各种课程中都会遇到，它是一个数学逻辑运算符号，在计算机中表示为“XOR”，在数学中表示为“![\\bigoplus][bigoplus]”

偏执的太偏执、/ 2021年11月10日 09:40/ 0 赞/ 210 阅读