此文章可以使用目录功能哟↑(点击上方[+])
HDU 1098 Ignatius's puzzle
Accept: 0 Submit: 0
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
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
100
9999
Sample Output
no
43
Problem Idea
解题思路:
【题意】
定义一个函数f(x)=5*x^13+13*x^5+k*a*x,现在给你k的值,让你求最小的非负整数a,使得对于任意整数x,满足65|f(x)
【类型】
快速幂+欧拉函数+欧拉定理+gcd
【分析】
首先,我们来看函数f(x)
因为题目说对于任意整数x均满足65|f(x)
那么,我们不妨令x=1
则f(1)=5+13+ka=ka+18(k已知)
所以,题目就转变成求
ka + 18 ≡ 0 mod 65
即
ka ≡ 47 mod 65
咦,这不是一元模线性方程吗?
再转化
ka = 65y + 47
如果该方程存在公约数,那我们还可以再化简
若gcd(k,64)|47不成立,则方程无解,输出"no"
化简之后,我们要开始求方程的解了
首先,了解一下欧拉函数φ(n)表示n以内与n互质的数的个数
再了解一下欧拉定理
那么
结合k*a ≡ 47 mod 65,可得题目所要求解的最小非负整数a的值为
【时间复杂度&&优化】
O(n)
题目链接→HDU 1098 Ignatius's puzzle
Source Code
/*Sherlock and Watson and Adler*/
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<cmath>
#include<complex>
#include<string>
#include<algorithm>
#include<iostream>
#define eps 1e-8
#define LL long long
#define bitnum(a) __builtin_popcount(a)
using namespace std;
const int N = 50005;
const int M = 5005;
const int inf = 1000000007;
const int mod = 1000000007;
__int64 Quick_Mod(int a, int b, int m)
{__int64 res = 1,term = a % m;while(b){if(b & 1) res = (res * term) % m;term = (term * term) % m;b >>= 1;}return res%m;
}
int euler(int n)
{int ans=n;for(int i=2;i*i<=n;i++)if(n%i==0){ans=ans-ans/i;while(n%i==0)n/=i;}if(n>1)ans=ans-ans/n;return ans;
}
int gcd(int a,int b)
{if(a%b)return gcd(b,a%b);return b;
}
int main()
{//ka ≡ 47 mod 65//ka = 65y + 47int k,g,b,m;while(~scanf("%d",&k)){b=47,m=65;g=gcd(k,m);if(b%g){puts("no");continue;}k/=g;m/=g;b/=g;printf("%I64d\n",b*Quick_Mod(k,euler(m)-1,m)%m);}return 0;
}