杭电 acm 1098

2024-08-27 04:18

文章标签 1098 杭电 acm

本文主要是介绍杭电 acm 1098，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

多校综合排名前25名的学校请发送邮件到HDUACM@QQ.COM,告知转账信息（支付宝或者卡号）

Ignatius's puzzle

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 6372 Accepted Submission(s): 4414

Problem Description

Ignatius is poor at math,he falls across a puzzle problem,so he has no choice but to appeal to Eddy. this problem describes that:f(x)=5*x^13+13*x^5+k*a*x,input a nonegative integer k(k<10000),to find the minimal nonegative integer a,make the arbitrary integer x ,65|f(x)if

no exists that a,then print "no".

Input

The input contains several test cases. Each test case consists of a nonegative integer k, More details in the Sample Input.

Output

The output contains a string "no",if you can't find a,or you should output a line contains the a.More details in the Sample Output.

Sample Input

      11
100
9999

Sample Output

      22
no
43

我的AC代码：

#include<stdio.h>
#include<math.h>
int main(){int a,k,n;while(scanf("%d",&k)!=EOF){               for(a=0;a<65;a++){n=a;              if((n*k)%5==2&&(n*k)%13==8){printf("%d\n",n);break;           }}if(a>64){printf("no\n");}}
}

明白了结论，虽然代码AC了，可是还是有些不清楚费马小定理。

以下是网上了解到的两种解题说法，顺便记录以便日后深入理解。

一、数学归纳法 f(x)=5*x^13+13*x^5+k*a*x
假设当x=n时 65|f(x)成立，那一定有 65|f(n+1)成立
那么65|f(n+1)-f(n) 成立通过二项展开可以得到只要18+k*a可以被65整除就可以了
在0~64之间遍历就ok。

其程序例子如下：

#include <stdio.h>
#include <math.h>
int main()
{int k,x,a,ans;while(scanf("%d",&k)!=EOF){for(a=1;a<=65;a++){for(x=0;x<65;x++){ans=18+k*a;if(ans%65)break;elsecontinue;}if(x==65){printf("%d\n",a);break;}}if(a==66)printf("no\n");}
}

二、 f(x)=5*x^13+13*x^5+k*a*x=x(5*x^12+13*x^4+k*a)，这个函数的形式直接就是费马小定理的形式费马小定理是数论中的一个重要定理,其内容为: 假如p是质数，且(a,p)=1，那么 a^(p-1) ≡1（mod p）假如p是质数，且a,p互质，那么 a的(p-1)次方除以p的余数恒等于1 对f(x)=x(5*x^12+13*x^4+k*a)用此定理分析：

（1）如果x是65的倍数，那么已经符合65整除f(x)
（2）如果x是5的倍数，只要5*x^12+13*x^4+k*a被13整除即可，去掉13的倍数13*x^4，也即5*x^12+k*a被13整除，由费马小定理，5与13互质，13是质数，所以x^(13-1)模13余1，所以5*x^12模13余5，要使5*x^12+k*a被13整除，k*a必须模13余8(k*a≡8(mod 13))
（3）如果x是13的倍数，类似（2），需要13*x^4+k*a被5整除，由费马小定理类似得到x^4模5余1，所以13*x^4模5余3，k*a必须模5余2(k*a≡8(mod 13))
（4）如果x不含5和13这两个因子，则需要5*x^12+13*x^4+k*a被65整除了，等价于既要被5整除，又要被13整除，就相当于以上(2)(3)两种情况的条件要同时满足，所以有 k*a≡2(mod 5) 并且 k*a≡8(mod 13) ，代码例子如下：

#include<iostream>
using namespace std;
int main()
{int k,i,flag;while(cin>>k){for(i=1;i<66;i++){if(i*k%13==8&&i*k%5==2) {flag=i;break;}else flag=0;}if(flag!=0)cout<<flag<<endl;else cout<<"no"<<endl;}return 0;
}

这篇关于杭电 acm 1098的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！