HDU 1098 Ignatius's puzzle(数论-其它)

By | 08月05日
Advertisement

Ignatius's puzzle

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

Author

eddy

Recommend

We have carefully selected several similar problems for you: 1071 1014 1052 1097 1082

题目大意:

给定一个k,找到最小的a 使得 f(x)=5*x^13+13*x^5+k*a*x ,f(x)%65永远等于0

解题思路:

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

所以 f(x+1)=f (x) + 5*( (13 1 ) x^12 ...... .....+(13 13) x^0 )+ 13*( (5 1 )x^4+...........+ ( 5 5 )x^0 )+k*a

除了5*(13 13) x^0 、13*( 5 5 )x^0 和k*a三项以外,其余各项都能被65整除.

那么也只要求出18+k*a能被65整除就可以了。

18+k*a=65*b

ax+by = c的方程有解的一个充要条件是:c%gcd(a, b) == 0

解题代码:“

#include <iostream>
#include <cstdio>
using namespace std;

int gcd(int a,int b){
    return b>0?gcd(b,a%b):a;
}

int main(){
    int k;
    while(scanf("%d",&k)!=EOF){
        if(18%gcd(k,65)==0){
            for(int a=0;;a++){
                if( (18+k*a)%65==0 ){
                    printf("%d\n",a);
                    break;
                }
            }
        }
        else printf("no\n");
    }
    return 0;
}

Similar Posts:

  • HDU 1098 Ignatius&#39;s puzzle

    Ignatius's puzzle Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 8526 Accepted Submission(s): 5907 Problem Description Ignatius is poor at math,he falls across a puzzle problem,so he has no choic

  • HDU 1098 Ignatius&#39;s puzzle 【数学(特殊值总结) Or 规律(瞎搞)】

    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

  • Hdu 1098 Ignatius&amp;amp;#39;s puzzle

    1.一开始读题,65|f(x)是什么意思都不清楚,最后百度才知道是f(x)能被65整除. 2.而且写这题完全没有思路,数论不好,我是根据网上的思路写的. 思路:则f(x+1 ) = f (x) + 5*( (13 1 ) x^12 ...... .....+(13 13) x^0 )+ 13*( (5 1 )x^4+...........+ ( 5 5 )x^0 )+k*a; 很容易证明,除了5*(13 13) x^0 .13*( 5 5 )x^0 和k*a三项以外,其余各项都能被65整除.那么

  • HDOJ 1098 Ignatius&#39;s puzzle

    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

  • hdu 1097 A hard puzzle 快速幂取模

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1097 分析:简单题,快速幂取模, 由于只要求输出最后一位,所以开始就可以直接mod10. /*A hard puzzle Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 33036 Accepted Submission(s): 11821 Pr

  • HDU 1028 Ignatius and the Princess III(母函数)

    题目:HDU-1028 题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1028 题目: Ignatius and the Princess III Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 16806 Accepted Submission(s): 11830 Problem Descri

  • 【搜索之BFS + 优先队列】杭电 hdu 1026 Ignatius and the Princess I

    /* THE PROGRAM IS MADE BY PYY */ /*----------------------------------------------------------------------------// Copyright (c) 2012 panyanyany All rights reserved. URL : http://acm.hdu.edu.cn/showproblem.php?pid=1026 Name : 1026 Ignatius and the Pri

  • HDU 1097 A hard puzzle【快速幂取模运算】

    A hard puzzle Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 30984 Accepted Submission(s): 11109 Problem Description lcy gives a hard puzzle to feng5166,lwg,JGShining and Ignatius: gave a and b,h

  • HDU 1027 Ignatius and the Princess II [康托逆展开]【数学】

    题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1027 --------------–. Ignatius and the Princess II Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 7182 Accepted Submission(s): 4264 Problem Descript

  • hdu 1299 Diophantus of Alexandria (数论)

    Diophantus of Alexandria Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 2269 Accepted Submission(s): 851 Problem Description Diophantus of Alexandria was an egypt mathematician living in Alexandr

Tags: