HDOJ 1098 ”Ignatius's puzzle“

桃扇骨 2022-05-19 03:11 55阅读 0赞

原题链接：[http://acm.hdu.edu.cn/showproblem.php?pid=1098][http_acm.hdu.edu.cn_showproblem.php_pid_1098]

<table> 
 <tbody> 
  <tr> 
   <td> <p>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&lt;10000),to find the minimal nonegative integer a,make the arbitrary integer x ,65|f(x)if<br> no exists that a,then print "no".</p> &nbsp; <p>Input</p> <p>The input contains several test cases. Each test case consists of a nonegative integer k, More details in the Sample Input.</p> &nbsp; <p>Output</p> <p>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.</p> &nbsp; <p>Sample Input</p> <p>11 100 9999</p> &nbsp; <p>Sample Output</p> <p>22 no 43</p> </td> 
  </tr> 
 </tbody> 
</table>

注：65|f(x)是f(x)能被65整除。

此题属于数论里面的费马小定理：

是[数论][Link 1]中的一个重要定理，其内容为：

假如p是[质数][Link 2]，且gcd(a,p)=1，那么 a(p-1)≡1（mod p）。即：假如a是整数，p是质数，且a,p互质(即两者只有一个公约数1)，那么a的(p-1)次方除以p的余数恒等于1。

a^(p-1)%p=1

(其中%为取模操作，且a<p，**p为质数**)

#include <stdio.h>
    #include <stdlib.h>
    #include <string.h>
    
    int main()
    {
        int k;
        while(~scanf("%d", &k))
        {
            int i;
            for(i=1;i<=65;i++){
                 if((18+k*i)%65==0)
                 {
                     printf("%d\n",i);
                     break;
                 }
                
            }
           if(i>65)
               printf("no\n");
               
        }
        return 0;
    }

[http_acm.hdu.edu.cn_showproblem.php_pid_1098]: http://acm.hdu.edu.cn/showproblem.php?pid=1098
[Link 1]: http://www.cnblogs.com/zxqxwnngztxx/p/6740950.html
[Link 2]: http://www.cnblogs.com/zxqxwnngztxx/p/6735297.html