题目链接
CF589_C Primes and Multiplication
题解
官方题解
官方题解
题解解释
题解中的式子
算法优化式子的解释
左边两项相当于1到n,各项找p的最大幂的因子(我们需要的是那个幂),大多数项是0次幂,即最大因子为1,其他的都是1到n中恰好为p的幂次,而且这个幂次只出现一次! —> 然后获取所有的幂次和
右边的式子则是让n值不断除p(记录第i次相除,i从1到$\Bigl \lfloor \frac{n}{p} \Bigr \rfloor$),在第i次判断n内各个数的集合中的因子含有$p^i$的数字个数,记录这些个数的和值
因为最终两个和值都是记录的1到n中所有数的p的因子出现次数,所以是相等的!(没看懂没有关系,看后面的例子体会一下)
h(i,p) 解释
- p是素数,然后h(i,p)表示p的多少次方等于i
- 即 $p^{h(i,p)}$ = i
举例解释
![]()
AC代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
| #include<bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i, a, b) for(int i = int(a); i <= int(b); ++i) #define per(i, b, a) for(int i = int(b); i >= int(a); --i) #define mem(x, y) memset(x, y, sizeof(x)) #define SZ(x) x.size() #define mk make_pair #define pb push_back #define fi first #define se second const ll mod=1000000007; const int inf = 0x3f3f3f3f; inline int rd() {int x=0;char p=getchar();while(p<'0'||p>'9')p=getchar();while(p>='0'&&p<='9')x=x*10+p-'0',p=getchar();return x;} inline ll qpow(ll a,ll b){ll ans=1%mod;for(;b;b>>=1){if(b&1)ans=ans*a%mod;a=a*a%mod;}return ans;} ll x,n,ans=1;
ll f(ll p){ ll m=n,sum=0; while(m) m/=p,sum+=m; return qpow(p,sum); }
int main(){ scanf("%lld%lld",&x,&n); for(int i=2;i*i<=x;i++){ if(x%i==0){ ans=ans*f(i)%mod; while(x%i==0) x/=i; } } if(x!=1) ans=ans*f(x)%mod; printf("%I64d\n",ans);
return 0; }
|
每天一句叨叨
哭过,痛苦过,但从没有放弃过。笑过,坚持过,因此不曾后悔过。