HDU Ignatius‘s puzzle

题目大意:f(x)=5*x^13+13*x^5+k*a*x,输入一个无负整数 k(k<10000),要找到最小的非负整数 a,将任意整数 x ,65|f(x),如果不存在该 a,则打印 “no”。

思路:这题有两种解法。第一种数学归纳法,第二种用费马小定理。

第一种:数学归纳法

1.当 x = 0 时,f ( 0 ) = 0 ,能被65整除。

2.当 x = x 时,f(x)=5*x^13+13*x^5+k*a*x能被65整除,那么 f ( x + 1 ) 肯定也是能被65整除的

3.当 x = x + 1 时,

f(x + 1 )= 5*(x+1)^13+13*(x+1)^5+k*a*(x + 1)

f(x + 1 )=5*(C_{13}^{0}x^{13}+C_{13}^{1}x^{12}+C_{13}^{2}x^{11}+...+C_{13}^{12}x^{1}+C_{13}^{13}x^{0})+

                        13*(C_{5}^{0}x^{5}+C_{5}^{1}x^{4}+...+C_{5}^{4}x^{1}+C_{5}^{5}x^{0})+k*a*(x + 1)

f(x + 1 )=f(x)+5*(C_{13}^{1}x^{12}+C_{13}^{2}x^{11}+...+C_{13}^{12}x^{1}+1)+

                        13*(C_{5}^{1}x^{4}+...+C_{5}^{4}x^{1}+1)+k*a

f(x + 1 )=f(x)+5*(C_{13}^{1}x^{12}+C_{13}^{2}x^{11}+...+C_{13}^{12}x^{1})+13*(C_{5}^{1}x^{4}+...+C_{5}^{4}x^{1})+ka+18

由(2)可知,f ( x ) 能被65整除,

5*(C_{13}^{1}x^{12}+C_{13}^{2}x^{11}+...+C_{13}^{12}x^{1})+13*(C_{5}^{1}x^{4}+...+C_{5}^{4}x^{1}) 也能被65整除,

所以只要当 k * a + 18 能被65整除就存在 a,否则不存在 a。

代码如下:

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
signed main(){int n;while(cin >> n){n%=65;int f=1;for(int i=0;i<=64;i++){if((18+n*i)%65==0){cout << i << endl;f=0;break;}}if(f) cout << "no" << endl;}return 0;
}

第二种:费马小定理(a^{p-1}%p=1)

要 f ( x ) %65==0 , 即f ( x ) %13==0 && f ( x ) %5==0,所以可以分成两部分计算。

1.f(x)=5*x^13+13*x^5+k*a*x

   f(x)=x*(5*x^12+13*x^4+k*a)%13=0 , 即 (5*x^12+13*x^4+k*a)%13=0

  因为13*x^4 %13=0                                                    (5*x^12+k*a)%13=0

由费马小定理可得,x^12%13=1                                         (k *a+5)%13=0

2.f(x)=5*x^13+13*x^5+k*a*x

   f(x)=x*(5*x^12+13*x^4+k*a)%5=0 , 即 (5*x^12+13*x^4+k*a)%5=0

因为 5*x^12%5=0                                                      (13*x^4+k*a)%5=0

由费马小定理可得,x^4%5=1                                         (k *a+13)%5=0

综上所述,当 (k *a+5)%13=0 && (k *a+13)%5=0 时 存在 a ,否则不存在 a。

代码如下:

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
signed main(){int n;while(cin >> n){int f=1;n%=65;for(int i=0;i<=64;i++){if(n*i%5==2 && n*i%13==8){cout << i << endl;f=0;break;}}if(f) cout << "no" << endl;}return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/450572.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

矩阵AB=0

矩阵AB0的性质 一、二的证明 这里还有一种说法 三、四的证明 详情请跳转五

linux环境下的程序设计与git操作

目录 前言&#xff1a; 进度条小程序&#xff1a; 先介绍几个背景知识 代码实现 Git操作 总结 其他指令 前言&#xff1a; 本文将重点介绍1. linux下的程序设计&#xff0c;并使用linux下的几个函数接口。实现一个简单的小程序 2.本着开源精神&#xff0c;进行git操作。…

数据同步工具Sqoop原理及场景优化

目录 0 数据同步策略 1 数据同步工具 ​编辑 2 Sqoop同步数据原理分析 2.1 原理分析 2.2 Sqoop基本使用分析 3 切片逻辑 3.1 MR切片逻辑 3.2 Hive CombineInputformat切片逻辑 3.3 实验1:Map任务并行度分析1 3.4 实验2: Map任务并行度分析2 3.5 实验3:Map任务并行…

SDIO - DWC MSHC 电压切换和频率切换

背景 我们的sdio访问sd card过去一直跑在低频上&#xff0c;HS50M。前段时间给eMMc添加了HS200模式&#xff0c;eMMc的总线模式定义是这样的&#xff1a; 可以看到1.8V的IO 电压可以支持所有模式&#xff0c;我们过去的芯片&#xff0c;由硬件部门放到evb上&#xff0c;其IO …

【学习笔记】什么是MongoDB

文章目录 MongoDB 简介体系结构数据模型MongoDB 的特点 MongoDB 简介 学习一个东西就跟认识一个人一样&#xff0c;下面有情MongoDB来做个自我介绍 大家好&#xff0c;俺是MongoDB&#xff0c;是一个开源、高性能、无模式的文档型数据库&#xff0c;当初的设计俺就是用于简化开…

Redis-03 持久化(RDB, AOF,混合持久化)及原理

1&#xff0c;持久化 Redis的持久化是必须的&#xff0c;当Redis服务宕机后&#xff0c;如果没有持久化&#xff0c;重启服务后redis中的数据都将丢失&#xff0c;所有的数据操作都将直连数据库&#xff0c;系统性能会大幅降低&#xff0c;所以在使用Redis做缓存服务时必须持久…

LabVIEW离心泵振动监控与诊断系统

利用LabVIEW结合数据采集与处理技术&#xff0c;构建了一套高效、低成本的振动监测与诊断系统&#xff0c;有效提升了测试精度与设备可靠性。 项目背景 在化工生产中&#xff0c;离心泵作为关键设备&#xff0c;其稳定运行对保障生产安全与效率至关重要。由于传统振动测试系统…

#数据结构(一)

线性表 两者都属于线性表线性表&#xff1a;逻辑结构------必连续      物理结构------不一定连续顺序表的物理结构 -----连续 &#xff0c;链表的物理结构 ----不连续顺序表的本质是数组&#xff0c;数组是一块地址连续的空间。而链表只是像细线一样&#xff0c;将不同地址…

LabVIEW提高开发效率技巧----VI继承与重载

在LabVIEW开发中&#xff0c;继承和重载是面向对象编程&#xff08;OOP&#xff09;中的重要概念。通过合理运用继承与重载&#xff0c;不仅能提高代码的复用性和灵活性&#xff0c;还能减少开发时间和维护成本。下面从多个角度介绍如何在LabVIEW中使用继承和重载&#xff0c;并…

萤石云服务支持云端视频AI自动剪辑生成

萤石视频云存储及媒体处理服务是围绕IoT设备云端存储场景下的音视频采集、媒体管理、视频剪辑和分发能力的一站式、专业云服务&#xff0c;并可面向广大开发者提供复杂设备存储场景下的完整技术方案。目前该服务新增了视频剪辑功能&#xff0c;支持将视频片段在云端进行裁剪并拼…

sentinel dashboard分布式改造落地设计实现解释(二)-分布式discovery组件

discovery discovery负责维护app/机器资料库&#xff0c;transport健康检测&#xff0c; transport上下线处理。discovery关键是分布式存储&#xff0c;后续研究一下raft&#xff0c;其复制&#xff0c;状态机&#xff0c;快照技术&#xff0c;但个人觉得&#xff0c;discover…

胤娲科技:AI短视频——创意无界,即梦启航

在这个快节奏的时代&#xff0c;你是否曾梦想过用几秒钟的短视频&#xff0c;捕捉生活中的每一个精彩瞬间&#xff1f;是否曾幻想过&#xff0c;即使没有专业的摄影和剪辑技能&#xff0c;也能创作出令人惊艳的作品&#xff1f; 现在&#xff0c;这一切都不再是遥不可及的梦想。…

基于光度学的小型视触觉传感器的开发

近年来&#xff0c;视觉触觉传感器&#xff08;VTS&#xff09;在机器人领域得到了广泛关注。传统的触觉传感器如压阻式、压电式和电容式触觉传感器在机器人感知方面有显著优势&#xff0c;但其分辨率相对较低。视触觉传感器使用相机获取触觉信息&#xff0c;能够提供高分辨率和…

执行jar文件no main manifest attribute错误

执行jar文件no main manifest attribute错误 问题是由于maven打包时候没有指定主启动程序&#xff0c;或下方配置中多余true配置跳过主程序配置 对应找到build中的所有有关true的删除&#xff0c;再重新打包即可

open-cd中的changerformer网络结构分析

open-cd 目录 open-cd1.安装2.源码结构分析主干网络1.1 主干网络类2.neck2.Decoder3.测试模型6. changer主干网络 总结 该开源库基于&#xff1a; mmcv mmseg mmdet mmengine 1.安装 在安装过程中遇到的问题&#xff1a; 1.pytorch版本问题&#xff0c;open-cd采用的mmcv版本比…

Axure重要元件一——动态面板

亲爱的小伙伴&#xff0c;在您浏览之前&#xff0c;烦请关注一下&#xff0c;在此深表感谢&#xff01; 本节课&#xff1a;动态面板 课程内容&#xff1a;认识动态面板、动态面板基本操作 应用场景&#xff1a;特定窗口、重要交互、长页面、容器等 一、认识动态面板 动态…

flutter TabBar自定义指示器(带文字的指示器、上弦弧形指示器、条形背景指示器、渐变色的指示器)

带文字的TabBar指示器 1.绘制自定义TabBar的绿色带白色文字的指示器 2.将底部灰色文字与TabrBar层叠&#xff0c;并调整高度位置与胶囊指示器重叠 自定义的带文字的TabBar指示器 import package:atui/jade/utils/JadeColors.dart; import package:flutter/material.dart; im…

用户界面设计:视觉美学与交互逻辑的融合

1、什么是用户界面 用户界面&#xff08;UI&#xff09;是人与机器之间沟通的桥梁&#xff0c;同时也是用户体验&#xff08;UX&#xff09;的重要组成部分。用户界面设计包括两个核心要素&#xff1a;视觉设计&#xff08;即产品的外观和感觉&#xff09;和交互设计&#xff…

【JavaEE初阶】深入理解TCP协议中的封装分用以及UDP和TCP在网络编程的区别

前言 &#x1f31f;&#x1f31f;本期讲解关于TCP/UDP协议的原理理解~~~ &#x1f308;上期博客在这里&#xff1a;【JavaEE初阶】入门视角-网络原理的基础理论的了解-CSDN博客 &#x1f308;感兴趣的小伙伴看一看小编主页&#xff1a;GGBondlctrl-CSDN博客 &#x1f525; …

Android Framework AMS(09)service组件分析-3(bindService和unbindService关键流程分析)

该系列文章总纲链接&#xff1a;专题总纲目录 Android Framework 总纲 本章关键点总结 & 说明&#xff1a; 说明&#xff1a;上上一章节主要解读应用层service组件启动的2种方式startService和bindService&#xff0c;以及从APP层到AMS调用之间的打通。上一章节我们关注了s…