2018 ACM-ICPC 宁夏网络赛 B-题Goldbach(米勒 罗宾算法)_goldbach's conjecture is one of the oldest and bes-程序员宅基地

技术标签: 算法题目练习与总结  

                                                                B Goldbach

Description:

Goldbach's conjecture is one of the oldest and best-known unsolved problems in number theory and all of mathematics. It states:

Every even integer greater than 2 can be expressed as the sum of two primes.

The actual verification of the Goldbach conjecture shows that even numbers below at least 1e14 can be expressed as a sum of two prime numbers. 

Many times, there are more than one way to represent even numbers as two prime numbers. 

For example, 18=5+13=7+11, 64=3+61=5+59=11+53=17+47=23+41, etc.

Now this problem is asking you to divide a postive even integer n (2<n<2^63) into two prime numbers.

Although a certain scope of the problem has not been strictly proved the correctness of Goldbach's conjecture, we still hope that you can solve it. 

If you find that an even number of Goldbach conjectures are not true, then this question will be wrong, but we would like to congratulate you on solving this math problem that has plagued humanity for hundreds of years.

Input:

The first line of input is a T means the number of the cases.

Next T lines, each line is a postive even integer n (2<n<2^63).

Output:

The output is also T lines, each line is two number we asked for.

T is about 100.

本题答案不唯一,符合要求的答案均正确

 

样例输入

1
8

样例输出

3 5

题目大意:给你一个很大的数,让你把这个数分成多个质数。(这些质数和==这个很大的数)

 

思路:(模版题)米勒罗宾-素数判定法(大素数判定)<高效>

话不多说,直接上代码:

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#define LL unsigned long long//注意这个longlong的定义,必须有 unsigned 

using namespace std;
//米勒 罗宾算法模版 ==============//
LL prime[6] = {2, 3, 5, 233, 331};
LL qu(LL x, LL y, LL mod) {
    LL ret = 0;
    while(y) {
        if(y & 1)
            ret = (ret + x) % mod;
        x = x * 2 % mod;
        y >>= 1;
    }
    return ret;
}
LL qpow(LL a, LL n, LL mod) {
    LL ret = 1;
    while(n) {
        if(n & 1) ret = qu(ret, a, mod);
        a = qu(a, a, mod);
        n >>= 1;
    }
    return ret;
}
bool MR(LL p) {
    if(p < 2) return 0;
    if(p != 2 && p % 2 == 0) return 0;
    LL s = p - 1;
    while(! (s & 1)) s >>= 1;
    for(int i = 0; i < 5; ++i) {
        if(p == prime[i]) return 1;
        LL t = s, m = qpow(prime[i], s, p);
        while(t != p - 1 && m != 1 && m != p - 1) {
            m = qu(m, m, p);
            t <<= 1;
        }
        if(m != p - 1 && !(t & 1)) return 0;
    }
    return 1;
}
//============================================//

int main()
{
	// MR(p)用这个方法,判定大数p是不是素数 
    LL p;
    int t;
    cin>>t;
    while (t)
    {
		cin>>p;
        if (MR(p-2) ) {
             cout<<"2"<< " "<<p-2;     continue;
	}
        for(LL i=3;i<=p/2;i+=2){
            if (MR(i) )
        	if(MR(p-i)){
        	   cout<<i<<" "<<p-i<<endl;
        			break;
		    }
	      }
        t--;
    }
    return 0;
}

 

    

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_38749759/article/details/80042527

智能推荐

18.12.5_linux installer for c2000 cgt-程序员宅基地

文章浏览阅读142次。dumpbin使用查看lib导出函数https://blog.csdn.net/ermen2009/article/details/17964813_linux installer for c2000 cgt

android kt框架,GitHub - bitxiao/KtArmor-MVVM: Android快速开发框架, KtArmor 寓意着 为Android 赋予战斗装甲, 方便开发者快速进行An...-程序员宅基地

文章浏览阅读479次。前言学习了Kotlin有一段时间了, 每次写项目/Demo的时候, 总是用到网络请求、MVP、MVVM、常用工具类、通用自定义View, 索性把这些整合到一起, 搭成一个Android的脚手架——KtArmor. 框架是我个人经验的积累, 总结. 如有不妥, 望各位大佬指出.什么是KtArmor ?KtArmor 寓意着 为Android 赋予战斗装甲, 方便开发者快速进行Android 开发。节..._android kt

linux共享动态库中同名对象重复析构-两次析构或多次析构引起的double free解决办法_全局变量跨dll 调用导致析构double free-程序员宅基地

文章浏览阅读2.1k次。原文链接:http://chengxu.org/p/541.htmlLinux 平台下的共享动态库,一般都是通过选项“-fPIC”编译出来。有些应用程序需要链接多个共享库,此时如果在这些共享库中存在相同作用域范围的同名静态成员变量,那么当程序访问完静态成员变量结束析构时,由于内存的 double free 会导致程序 core dump;该问题是由于 Linux 编译器的缺陷造成的,本文就此问题进..._全局变量跨dll 调用导致析构double free

Golang 常见设计模式之装饰模式_goland 装饰模式-程序员宅基地

文章浏览阅读2.4k次,点赞4次,收藏3次。尽管 Go 语言中装饰模式没有 Python 中应用的那么广泛,但是它也有其独到的地方。接下来就一起看下装饰模式在 Go 语言中的应用。_goland 装饰模式

Orthogonal Convolutional Neural Networks_orthognal convolution neural-程序员宅基地

文章浏览阅读1.2k次,点赞2次,收藏2次。文章目录概主要内容符号说明Y=Conv(K,X)Y=Conv(K,X)Y=Conv(K,X)的俩种表示Y=KX~Y=K\tilde{X}Y=KX~Y=KXY=\mathcal{K}XY=KXkernel orthogonal regularizationorthogonal convolutionWang J, Chen Y, Chakraborty R, et al. Orthogonal ..._orthognal convolution neural

Windows7 Server 2008 下安装Oracle 10g提示“程序异常终止,发生未知错误”的解决方法_oracle10程序异常终止一 windows 2008-程序员宅基地

文章浏览阅读7.3k次。我的Oracle 10g版本是10.2.0.1.0,选择高级安装,提示“程序异常终止,发生未知错误”。1.修改Oracle 10G\database\stage\prereq\db\refhost.xml在 后面添加 2.到install目录中找到oraparam.ini文件,把#Windows=4.0,5.0,5.1,5.2修_oracle10程序异常终止一 windows 2008

随便推点

123456_使用fdisk对磁盘进行分区时,lvm分区的类型为-程序员宅基地

文章浏览阅读694次。1_使用fdisk对磁盘进行分区时,lvm分区的类型为

内存管理之程序内存分布-程序员宅基地

文章浏览阅读377次。在多任务操作系统中的每一个进程都运行在一个属于它自己的内存沙盘中。这个沙盘就是虚拟地址空间(virtual address space)。1 32位虚拟内存布局在32位模式下虚拟地址空间总是一个4GB的内存地址块。这些虚拟地址通过页表(page table)映射到物理内存,页表由操作系统维护并被处理器引用。每一个进程拥有一套属于它自己的页表,但是还有一个隐情。只要虚拟地址被使用,那么...

Bootstrap3 全局样式_bootstrap3 权限选择样式-程序员宅基地

文章浏览阅读423次。Bootstrap 3 的目标是简洁、直观、强悍的前端开发框架,让 Web 开发变得更好、更快、更强壮,我们有必要先了解一下 Bootstrap 底层结构的关键部分。 HTML5文档类型Bootstrap使用了HTML5特定的元素和CSS属性,在使用Bootstrap的时候,所有HTML文档的第一行代码必须是 <!DOCTYPE html>。如:<!DOCTYPE h..._bootstrap3 权限选择样式

linux管道举例理解_linux中的管道举例-程序员宅基地

文章浏览阅读4.7k次,点赞24次,收藏89次。linux管道举例理解一、管道的定义:“|”二、查找2.1统计当前目录下有多少个文件2.2查看当前目录下的前n(3)个文件2.3查看wang.txt文件包含i的字符行2.4查看内存使用情况2.5查询进程三、更改一、管道的定义:“|”一般我们在进行操作的时候,命令很多,但我们只想要其中一部分,那么就可以使用管道了。管道是Linux中很重要的一种通信方式,是把一个前一个结果的输出直接连接到另一个..._linux中的管道举例

hdu 1686 kmp Oulipo-程序员宅基地

文章浏览阅读499次。http://acm.hdu.edu.cn/showproblem.php?pid=1686对于我这种刚开始学的人来说 刚开始我觉的很难 不会做哦 但是看了一下别人的一下子就知道了 还是不是太熟了 需要加强练习哦 呵呵 其实这是一道简单的kmp 的算法 只要你在index_kmp() 将 i 的值一直小于N 就可以了 还是看看我具体

实战篇:Linux 安装 Oracle 11GR2 数据库保姆级教程_liunxoracle11gr2-程序员宅基地

文章浏览阅读2.1w次,点赞204次,收藏603次。没接触Linux的朋友不用害怕,跟着本篇文章一步步操作,安装Oracle如喝水般简单且标准。_liunxoracle11gr2

推荐文章

热门文章

相关标签