约数个数
基于算术基本定理
N = (p1^x1)(p2^x2)(p3^x3)…(pk^xk)
约数个数=(x1+1)(x2+1)(x3+1)…(xk+1)
为什么呢?简单证明如下
因为每一种pi都有0->xi种选法,一共xi+1种,一共k个所以迭代k次
这么讲不够直白,接下来举个栗子
24=2*2*2*3=2³*3
再用各个质数的指数加一后再相乘即为此数的约数个数,
比如 (3+1)*(1+1)=4*2=8, 即表示24有8个约数。
24的约数:1、2、3、4、6、8、12、24
算法1
思路就是先把原数分解为质因数,最后把每一个数的指数累加即可。从a1一直分解到an,由于a的数据过大,此处用哈希表进行存储。
C++ 代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int mod=1e9+7;
int main()
{
int n;
cin>>n;
unordered_map<int ,int >primes;//存储所有的底数和指数
while(n--)
{
int x;
cin>>x;
for(int i=2;i<=x/i;i++)
while(x%i==0)
{
x/=i;
primes[i]++;//i的质因数指数+1
}
if(x>1)primes[x]++;
}
//以上过程完成primes就存了所有质因数的指数
LL res=1;
for(auto prime:primes) res = res*(prime.second+1)%mod;
cout<<res<<endl;
return 0;
}
最喜欢讲概念举例子的
就稀罕你这种会举例子的
可太对了
有没有刷题群能拉一下我的?最近要秋招了没动力
各位佬儿,ans = ans*(i.second + 1) % (1e9 + 7)为什么不对呢?
orz
爱了爱了
栗子好评 good good 💎
我这种菜鸡看大佬举个例子立马就明白了,生推还是感觉抽象orz
爱了爱了,感觉你讲的言简意赅