QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#232670#959. Multiple?xztmax67TL 0ms0kbC++14523b2023-10-30 19:20:332023-10-30 19:20:33

Judging History

你现在查看的是最新测评结果

  • [2023-10-30 19:20:33]
  • 评测
  • 测评结果:TL
  • 用时:0ms
  • 内存:0kb
  • [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

output:


result: