ACwing求一个数约数个数

2024-02-04 23:48
文章标签 acwing 个数 约数

本文主要是介绍ACwing求一个数约数个数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

 

给定 n 个正整数 ai,请你输出这些数的乘积的约数个数,答案对 109+7 取模。

输入格式

第一行包含整数 n。

接下来 n 行,每行包含一个整数 ai。

输出格式

输出一个整数,表示所给正整数的乘积的约数个数,答案需对 109+7 取模。

数据范围

1≤n≤100,
1≤ai≤2×109

输入样例:

3
2
6
8

输出样例:

12

 公式:一个数的所有质因子为{P1,P2,P3,P4}

约数个数为(P1+1)*(P2+1)*(P3+1)*(P4+1)

#include<bits/stdc++.h>
using namespace std;
const int mod = 1e9+7;
unordered_map<int,int>vis;
int main()
{int n,x;cin>>n;while(n--){cin>>x;for(int i =2;i<=x/i;i++){if(x%i==0){while(x%i==0){vis[i]++;x/=i;}}}if(x!=1)vis[x]++;}long long ans = 1;for(auto it = vis.begin();it!=vis.end();it++){ans = ans*(it->second+1)%mod;}cout<<ans<<endl;return 0;
}

 

这篇关于ACwing求一个数约数个数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/679165

相关文章

spoj705( 求不相同的子串个数)

题意:求串s的不同子串的个数 解题思路:任何子串都是某个后缀的前缀,对n个后缀排序,求某个后缀的前缀的个数,减去height[i](第i个后缀与第i-1 个后缀有相同的height[i]个前缀)。 代码如下: #include<iostream>#include<algorithm>#include<stdio.h>#include<math.h>#include<cstrin

XTU 1233 n个硬币连续m个正面个数(dp)

题面: Coins Problem Description: Duoxida buys a bottle of MaiDong from a vending machine and the machine give her n coins back. She places them in a line randomly showing head face or tail face o

O(n)时间内对[0..n^-1]之间的n个数排序

题目 如何在O(n)时间内,对0到n^2-1之间的n个整数进行排序 思路 把整数转换为n进制再排序,每个数有两位,每位的取值范围是[0..n-1],再进行基数排序 代码 #include <iostream>#include <cmath>using namespace std;int n, radix, length_A, digit = 2;void Print(int *A,

【AcWing】851. 求最短路

spfa算法其实是对贝尔曼福特算法做一个优化。 贝尔曼福特算法会遍历所有边来更新,但是每一次迭代的话我不一定每条边都会更新,SPFA是对这个做优化。 如果说dist[b]在当前这次迭代想变小的话,那么一定是dist[a]变小了,只有a变小了,a的后继(b)才会变小。 用宽搜来做优化,用一个队列,队列里边存的就是所有变小了的结点(队列里存的是待更新的点)。 基本思路就是我更新过谁,我再拿

LCP 485. 最大连续 1 的个数[lleetcode -11]

从今天起,我们的算法开始研究搜索,首先就是DFS深度优先搜索(depth-first seach,DFS)在搜索到一个新的节点时,立即对该新节点进行遍 历;因此遍历需要用先入后出的栈来实现,也可以通过与栈等价的递归来实现。对于树结构而言, 由于总是对新节点调用遍历,因此看起来是向着“深”的方向前进。 下面是一个一维的DFS算法 LCP 485. 最大连续 1 的个数 给定一个二进制数组 nu

【AcWing】852. spfa判断负环

#include<iostream>#include<algorithm>#include<cstring>#include<queue>using namespace std;const int N= 1e5+10;int n,m;int h[N],w[N],e[N],ne[N],idx;int dist[N],cnt[N];//cnt存最短路径的边数bool st[N];v

双指针(5)_单调性_有效三角形的个数

个人主页:C++忠实粉丝 欢迎 点赞👍 收藏✨ 留言✉ 加关注💓本文由 C++忠实粉丝 原创 双指针(5)_单调性_有效三角形的个数 收录于专栏【经典算法练习】 本专栏旨在分享学习C++的一点学习笔记,欢迎大家在评论区交流讨论💌 目录 1. 题目链接: 2.题目描述 : 3.解法 :     解法一(暴力枚举) :     算法思路 :     代码展示 : 暴力枚

HDU2521(求因子个数)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=2521 解题思路: 数据量不大,直接O(n)遍历,对每个数求其因子个数,找出最大的即可。 完整代码: #include <functional>#include <algorithm>#include <iostream>#include <fstream>#includ

222.完全二叉树的节点个数

(写给未来遗忘的自己) 题目: 代码: class Solution {public:int countNodes(TreeNode* root) {queue<TreeNode*>node_que;if(root==nullptr) return 0;node_que.push(root);int result;while(!node_que.empty()){int layer_s

Kubernetes的alpha.kubernetes.io/nvidia-gpu无法限制GPU个数

问题描述: Pod.yaml文件中关于GPU资源的设置如下: 然而在docker中运行GPU程序时,发现宿主机上的两块GPU都在跑。甚至在yaml文件中删除关于GPU的请求,在docker中都可以运行GPU。 原因: 上例说明alpha.kubernetes.io/nvidia-gpu无效。查看yaml文件,发现该docker开启了特权模式(privileged:ture): 而