日期:2014-05-20 浏览次数:21152 次
Description 现有一公式:a^b mod c = X.给出a,b,c,求X。 注:c总是素数 Input Output Sample Input 3 8 13 2 3 11 Sample Output 3 8
Description 现有一公式:X^a mod b = c.给出a,b,c,求出所有满足条件的X。 输入包括多组数据,每组数据三个正整数1<=a,b,c<=10^7。 每组数据输出若干行,每一行代表了满足方程的一个X的解,解的顺序按照从小到大输出,最后输出一个空行。 没有解输出“No Solution!” 注:b总是素数 Input Output Sample Input 3 13 8 2 3 2 Sample Output 2 5 8
static void Main(string[] args) { int r = 0; r = Fx(3, 8, 13); Console.Write(r); r = Fx(2, 3, 11); Console.Write(r); Console.Read(); } static int Fx(int a, int b, int c) { int t = b >> 1; return (t>0?Fx((a*a)%c,t,c):1)*((b & 1)==0?1:a % c) % c; }
------解决方案--------------------
// Right-to-left binary method int Modular(int theBase, int exponent, int modulus) { int result = 1; while( exponent > 0 ) { if( (exponent & 1) == 1 ) { result = (result * theBase) % modulus; } exponent /= 2; theBase = (theBase * theBase) % modulus; } return result; }
------解决方案--------------------
第二题只想到这么一个算法
static void FX2(int a, int b, int c) { while (c < 10000000) { double x = Math.Pow( Math.E ,Math.Log(c)/a); if (Math.Round( x,8) == Math.Round(x)) { Console.WriteLine(Math.Round(x)); } c += b; } }
------解决方案--------------------
a^b mod c = X
首先计算a^1 mod c = ? a^2 mod c = ? ,直到a^n mod c =1,然后n为循环,计算b mod n,最后求出余数。
3^8 mod 13 = 9 ,不是3
------解决方案--------------------
第二题真没看懂,假定a=3 b=13 c=8
由 X^3 mod 13 = 8 可以推导得出 X^3=13*k +8(k为自然数)
由于k有无数个,可以推导出13k+8有无数个,等量替换,可以推导出X^3有无数个。从而可以得到,这样的X有无数个。。。。
我求出来 2,5,6,15,18,19,28,31,32,41,44,45,54,57,58,67,70,71,80,83....一大堆呢
------解决方案--------------------
string input = Console.ReadLine(); string[] nums = input.Split(' '); int x, a, b, c, tempResult; List<int> answer = new List<int>(); //a = Convert.ToInt32(nums[0]); a = Convert.ToInt32(nums[0]); b = Convert.ToInt32(nums[1]); c = Convert.ToInt32(nums[2]); for (x = 1; x <= 300; x++) { tempResult = 1; for (int times = 1; times <= a; times++) tempResult *= x; if (tempResult % b == c) answer.Add(x); } answer.ForEach(an => Console.WriteLine(an));