Pseudoprime numbers(POJ-3641 快速幂)

简介: Pseudoprime numbers(POJ-3641 快速幂)

快速幂:快速幂就是所求的幂次方过大,导致代码所用的时间超限。

如:求2^3,3的二进制是11,(n&1)判断次方数的二进制是否为1,n>>1,向右进位1:

代码:

k=1,t=n;
while(n)
  {
    if(n&1)//判断n的最后一位二进制不为0
    {
      k=k*m;
    }
    n=n>>1;
    m=m*m;
  }

题目描述:

Fermat’s theorem states that for any prime number p and for any integer a > 1, ap = a (mod p). That is, if we

raise a to the pth power and divide by p, the remainder is a. Some (but not very many) non-prime values of p,

known as base-a pseudoprimes, have this property for some a. (And some, known as Carmichael Numbers, are

Given 2 < p ≤ 1000000000 and 1 < a < p, determine whether or not p is a base-a pseudoprime.

Input
Input contains several test cases followed by a line containing "0 0". Each test case consists of a line containing p and a.
Output
For each test case, output "yes" if p is a base-a pseudoprime; otherwise output "no".
Sample Input
3 2
10 3
341 2
341 3
1105 2
1105 3
0 0
Sample Output
no
no
yes
no
yes
yes

解题思路:这个题理解起来就是两个函数去判断,对应输出yes/no,首先判断这个数是否为素数,然后再判断(a^p)%p==a就可以了,不过这个幂次方就是需要快速幂。

程序代码:

#include<stdio.h>
#include<math.h>
int  fn(long long n)
{
  long long i,j,k;
  k=sqrt(n);
  for(i=2;i<=k;i++)
  {
    if(n%i==0)
      return 0;
  }
  return 1;
}
int f(long long n,long long m)
{
  long long k,a,t;
  k=1,t=n;
  while(n)
  {
    if(n&1)
    {
      k=(k*m)%t;
    }
    n=n>>1;
    m=(m*m)%t;
  }
  return k;
}
int main()
{
  long long i,j,k,m,n;
  while(scanf("%lld%lld",&n,&m)!=EOF)
  {
    if(n==0&&m==0)
      break;
    if(fn(n)==1)
      printf("no\n");
    else
    {
      k=f(n,m);
      if(k==m)
        printf("yes\n");
      else
        printf("no\n");
    }
  }
  return 0;
}
















相关文章
|
11月前
|
前端开发
Bootstrap5 导航栏8
使用 `.navbar-text` 类可在导航栏中添加非链接文本,确保文本水平对齐且样式统一。示例代码展示了如何在 Bootstrap 导航栏中加入文本和链接。
|
安全 Java 索引
Java中的字符串String
Java中的字符串String
114 0
|
JSON Go 数据格式
Go语言:运行时反射,深度解析!
反射有两种类型 reflect.Value 和 reflect.Type ,分别表示变量的值和类型,并且提供了两个函数 reflect.ValueOf 和 reflect.TypeOf 分别获取任意对象的 reflect.Value 和 reflect.Type。
296 0
Go语言:运行时反射,深度解析!
|
Linux
【Linux线程同步专题】三、条件变量
【Linux线程同步专题】三、条件变量
163 0
|
移动开发
阿里小程序云应用开发指南
小程序云应用是面向小程序应用场景,为开发者提供的一键构建后端应用运行环境、后端服务部署、运维监控等能力的一站式小程序部署服务。 小程序云应用是小程序云的一个重要组成部分。小程序云是阿里云面向小程序场景提供的一站式云服务,帮助开发者实现一云多端的业务战略。
8157 0
|
3天前
|
存储 关系型数据库 分布式数据库
PostgreSQL 18 发布,快来 PolarDB 尝鲜!
PostgreSQL 18 发布,PolarDB for PostgreSQL 全面兼容。新版本支持异步I/O、UUIDv7、虚拟生成列、逻辑复制增强及OAuth认证,显著提升性能与安全。PolarDB-PG 18 支持存算分离架构,融合海量弹性存储与极致计算性能,搭配丰富插件生态,为企业提供高效、稳定、灵活的云数据库解决方案,助力企业数字化转型如虎添翼!
|
14天前
|
弹性计算 关系型数据库 微服务
基于 Docker 与 Kubernetes(K3s)的微服务:阿里云生产环境扩容实践
在微服务架构中,如何实现“稳定扩容”与“成本可控”是企业面临的核心挑战。本文结合 Python FastAPI 微服务实战,详解如何基于阿里云基础设施,利用 Docker 封装服务、K3s 实现容器编排,构建生产级微服务架构。内容涵盖容器构建、集群部署、自动扩缩容、可观测性等关键环节,适配阿里云资源特性与服务生态,助力企业打造低成本、高可靠、易扩展的微服务解决方案。
1305 5
|
13天前
|
机器学习/深度学习 人工智能 前端开发
通义DeepResearch全面开源!同步分享可落地的高阶Agent构建方法论
通义研究团队开源发布通义 DeepResearch —— 首个在性能上可与 OpenAI DeepResearch 相媲美、并在多项权威基准测试中取得领先表现的全开源 Web Agent。
1333 87