1 条题解
-
0
/* 基本的思路 首先化简可得(x+y)/(x*y)=1/n 关键一步:令 x=n+a y=n+b 这一步相当关键,整个题目的精髓所在。 因为x和y和n都是正整数,要想等式成立,x和y作为分母肯定都要大于n,不然等式成立不了 代入原公式化简得代入原公式化简得 n^2=ab 然后就等价于求解n^2的约数个数了 */ #include<bits/stdc++.h> using namespace std; typedef long long LL; const int mod=1e9+7,N=1e6+5; LL n,pr,prime[N]; bool v[N]; void get_prime() { pr=0;memset(v,0,sizeof(v)); for(LL i=2;i<=n;i++) { if(v[i]==0) prime[++pr]=i; for(int j=1;(j<=pr)&& (i*prime[j]<=n);j++) { v[ i * prime[j] ]=1; if( i % prime[j] ==0) break; } } } int main() { scanf("%lld",&n); get_prime(); LL ans=1; for(LL i=1;i<=pr;i++) { LL cnt=0; for(LL j=prime[i];j<=n;j*=prime[i]) cnt+=n/j; cnt%=mod; ans=ans*(cnt*2+1)%mod; } printf("%lld\n",ans); return 0; }
- 1
信息
- ID
- 1763
- 时间
- 1000ms
- 内存
- 512MiB
- 难度
- 6
- 标签
- 递交数
- 111
- 已通过
- 33
- 上传者