php网站后台模板,网站建设qinnet,高碑店住房和城乡建设局网站,php网站开发数据列表排重试除法求约数
时间复杂度 O(sqrt(n))。
核心思路是求到较小的约数时#xff0c;将其对应的较大约数也可以直接求出来#xff0c;
例如#xff1a;a/bc#xff0c;b是a的余数#xff0c;c也是a的余数
ps#xff1a;注意bc的情况#xff0c;要注意去重
void solve() …试除法求约数
时间复杂度 O(sqrt(n))。
核心思路是求到较小的约数时将其对应的较大约数也可以直接求出来
例如a/bcb是a的余数c也是a的余数
ps注意bc的情况要注意去重
void solve() {int n; cin n;vectorint ans;for (int i 1; i n / i; i) {if (n % i 0) {ans.push_back(i);if (i ! n / i) ans.push_back(n / i);//去重}}sort(ans.begin(), ans.end());for (auto x : ans) {cout x ;}cout endl;
} 前置知识分解质因数
n
p是质因数
void solve() {int n; cin n;mapint, int mp;int c; cin c;for (int i 2; i c / i; i) {while (c % i 0) {c / i;mp[i];}}if (c 1) mp[c];//如果c本身就是质数例如7//那么它就大于sqrt(c)因此要特判} 约数个数
假设现在有一个n它可以被分解为n
假设d是n的一个约数d可以被分解为 d
那么的不同表示的约数也就不同。且 0。
因此会有个约数。 const int mod 1e9 7;
void solve() {int n; cin n;mapint, int mp;while (n--) {int c; cin c;for (int i 2; i c / i; i) {while (c % i 0) {c / i;mp[i];}}if (c 1) mp[c];}int res 1;for (auto it : mp) {res res * (it.second 1) % mod;}cout res endl;
}signed main()
{int t; t 1;//cin t;while (t--) {solve();}return 0;
} 约数之和
前置知识秦九昭算法 秦九昭算法也称“快速幂求多项式值算法”是一种高效地计算一个多项式在某个点的取值的方法。它利用了快速幂算法的思想在O(logn)的时间复杂度内计算出多项式在某个点的值。 对于一个n次多项式f(x)它可以表示为 秦九昭算法利用了多项式的特殊性质将上述公式转化为如下形式 这个公式可以看作是从后往前逐项累加的过程每次累加时都将上一项的结果乘以x再加上当前项的系数。这个过程可以通过一个循环来实现每次迭代都将当前项的系数与上一次迭代的结果相乘再加上上一次迭代的结果最终得到多项式在x0处的值。
具体来说可以用如下的代码实现
double p a[n];
for (int i n - 1; i 0; --i) {p a[i] x * p;
}公式 原理把这个式子展开会发现枚举了每种约数指数不同约数就不同并将他们加起来便是约数之和了。 程序怎么写呢这里要用到秦九昭算法由于我们约数求和公式里的ai 1因此程序写成
int res 1;for (auto it : mp) {int p it.first, k it.second;int temp 1;while (k--) {temp (temp * p 1) % mod;}res res * temp % mod;}cout res endl; 完整代码
int mod 1e9 7;
void solve() {int n; cin n;mapint, int mp;while (n--) {int c; cin c;for (int i 2; i c / i; i) {while (c % i 0) {c / i;mp[i];}}if (c 1) mp[c];}int res 1;for (auto it : mp) {int p it.first, k it.second;int temp 1;while (k--) {temp (temp * p 1) % mod;}res res * temp % mod;}cout res endl;
}signed main()
{int t; t 1;//cin t;while (t--) {solve();}return 0;
} 最大公约数欧几里得算法
前置知识
若 a%d0b%d0则 (axby) % d 0 我们要求ab的最大公约数。假设最大公约数是d
公式 gcd(a,b) gcd(b,a%b)这是核心这个公式为什么成立呢往下看
原理因为 a%b a-()*b把设为c那么就是 a%b a-c*b
惊奇地发现这个式子满足(axby) % d 0。
因此对于 gcd(b,a%b)d是b和a%b的约数那么公式gcd(a,b) gcd(b,a%b)就成立了。
当b 0时此时的a就是最大公约数。
int gcd(int a, int b)
{return b 0 ? gcd(b, a % b) : a;
}