QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#232670 | #959. Multiple? | xztmax67 | TL | 0ms | 0kb | C++14 | 523b | 2023-10-30 19:20:33 | 2023-10-30 19:20:33 |
answer
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int power(int x,int y,int t=1){for(;y;y>>=1,x=x*x%mod)if(y&1)t=t*x%mod;}
int n,k,ans;
signed main()
{
scanf("%lld%lld",&n,&k);
int inv=1;ans=1;
for(int i=n-1;i>n-k;i--)ans=(ans*i)%mod;
for(int i=1;i<k;i++)inv=inv*i%mod;
ans=ans*power(inv,mod-2)%mod;
ans=ans*n;
for(int i=2;i*i<=n;i++)if(n%i==0)
{
ans=ans/i*(i-1);
while(n%i==0)n/=i;
}
if(n>1)ans=ans/n*(n-1);
printf("%lld\n",ans%mod);
return 0;
}
详细
Test #1:
score: 0
Time Limit Exceeded
input:
4 1