C / C ++程序用于模数方程的解数?
在数学上,从方程问题的角度来看,模方程是由模满足的代数方程。即,给定模空间上的多个函数,模方程是在它们之间保持的方程,换句话说,是模的恒等式。
术语模数方程的最常用用法是与椭圆曲线的模数问题有关。在那种情况下,模空间本身是一维的。这意味着在模块化曲线的函数字段中,任何两个有理函数F和G将满足模块化方程P(F,G)=0,其中P是复数上两个变量的非零多项式。对于F和G的合适的非简并选择,方程P(X,Y)=0将实际上定义模数曲线。
您刚刚看到了一种奇怪的形式的数学表达式
B≡(AmodX)
这表示B与A模X一致。让我们举个例子,
21≡5(mod4)
等价的符号表示“等效”。在上式中,21和5是等效的。这是因为21模4=1等于5模4=1。另一个例子是51≡16(mod7)
在这个问题中,我们有两个整数a和b,我们必须找到遵循模块化方程(AmodX)=B的可能值x的数量,其中,模块化方程的X解。
例如
Input: A = 26, B = 2 Output: X can take 6 values
说明
X可以等于{3,4,6,8,12,24}中的任何一个,因为这些值中的任何一个都等于2,即(26mod3)=(26mod4)=(26mod6)=(26mod8)=....=2
我们有方程式AmodX=B
条件
如果(A=B),那么将有无数个值,其中A总是大于X。
如果(A<B),则X不可能保存模方程。
现在只剩下最后一种情况(A>B)。
现在,在这种情况下,我们将使用关系
股息=除数*商+余数
X表示除数,A表示股息,B表示余数。
现在
A=X*商+B
让商表示为Y
∴A=X*Y+B
A-B=X*Y
∴为了获得Y的积分值,
我们需要取所有X使得X除以(A-B)
∴X是(A-B)的除数
找到(A–B)的除数是主要问题,而这种除数的数量就是X可以取的值。
我们知道AmodX解的值将是从(0到X–1)取所有这样的X,使得X>B。
这样,我们可以得出结论:(A–B)的除数大于B,并且所有可能的值X都可以满足AmodX=B
示例
#include <iostream> #include <math.h> using namespace std; int Divisors(int A, int B) { int N = (A - B); int D = 0; for (int i = 1; i <= sqrt(N); i++) { if ((N % i) == 0) { if (i > B) D++; if ((N / i) != i && (N / i) > B) D++; } } return D; } int PossibleWaysUtil(int A, int B) { if (A == B) return -1; if (A < B) return 0; int D = 0; D = Divisors(A, B); return D; } int main() { int A = 26, B = 2; int Sol = PossibleWaysUtil(A, B); if (Sol == -1) { cout <<" X can take Infinitely many values greater than " << A << "\n"; } else { cout << " X can take " << Sol << " values\n"; return 0; } }