数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
服装设计
法学在 C++ 中查找等差数列中第一个给定素数的倍数
概念
给定等差数列的首项 (A) 和公差 (d)，以及一个素数 (P)，我们的任务是确定该等差数列中第一个为给定素数 P 的倍数的元素的位置。
输入
A = 3, d = 4, P = 5
输出
3
解释
给定等差数列的第四项是素数 5 的倍数。
首项 = 3
第二项 = 3+4 = 7
第三项 = 3+2*4 = 11
第四项 = 3+3*4 = 15
方法
假设该项为 AN。因此，
AN = (A + (N-1)*d)
已知 AN 是 P 的倍数。因此，
A + (N-1)*d = l*P
这里，l 是一个常数。
假设 A 为 (A % P) 且 d 为 (d % P)。现在，我们有 (N-1)*d = (l*P – A)。
通过在 RHS 加上和减去 P，我们得到：
(N-1)*d = P(l-1) + (P-A),
在这种情况下，P-A 被视为非负数
(因为 A 被替换为 A%P，它小于 P) 最后对两边取模：
((N-1)*d)%P = (P-A)%P 或，((N-1)d)%P = P-A
假设计算一个 Y < P，使得 (d*Y)%P = 1。现在，这个 Y 被称为关于 P 的 d 的模反元素。
最终答案 N 为：
((Y*(P-A)) % P) + 1.
示例
#include <bits/stdc++.h>
using namespace std;
// Shows iterative Function to calculate
// (x1^y1)%p1 in O(log y1) */
int power(int x1, int y1, int p1){
// Used to initialize result
int res1 = 1;
// Used to update x if it is more than or
// equal to p
x1 = x1 % p1;
while (y1 > 0) {
// It has been seen that if y1 is odd, multiply x1 with
result
if (y1 & 1)
res1 = (res1 * x1) % p1;
// y1 must be even now
y1 = y1 >> 1; // y1 = y1/2
x1 = (x1 * x1) % p1;
}
return res1;
}
// Shows function to find nearest element in common
int NearestElement1(int A, int d, int P){
// Shows base conditions
if (A == 0)
return 0;
else if (d == 0)
return -1;
else {
int Y = power(d, P - 2, P);
return (Y * (P - A)) % P;
}
}
// Driver code
int main(){
int A = 3, d = 4, P = 5;
// Used to module both A and d
A %= P;
d %= P;
// Shows function call
cout << NearestElement1(A, d, P);
return 0;
}输出
3
更新于：2020年7月24日
45 次浏览
广告