LA 3521 Joseph's Problem

题意:给你正整数n和k,然后计算从i到n k%i的和;

思路;如果n小于1000000,直接暴力计算,然后大于1000000的情况,然后在讨论n和k的大小,根据k%i的情况,你会发现规律,是多个等差数列,然后你把这些等差数列加上就是答案。

 #include <cstdio>
#include <cstring>
#include <algorithm>
#define ll long long
using namespace std; ll n,k;
ll Getsum(ll n)
{
ll sum=;
for(ll i=; i<=n; i++)
{
sum+=k%i;
}
return sum;
} int main()
{
while(scanf("%lld%lld",&n,&k)!=EOF)
{
if(n<=)
{
printf("%lld\n",Getsum(n));
continue;
}
ll ans=;
ans+=max((ll),n-k)*k;
for(int i=; i<=; i++)
{
if(i>k) break;
ll x1=k/(i-)-k/i;
if(k/i>n)continue;
int s=k%(k/(i-)),e=k%(k/i+);
if(k/(i-)>n)
{ s=k%n;
x1=n-k/i;
}
ans+=(s+e)*x1/;
}
if(k>)
{
ll m=k/;
ans+=Getsum(m);
}
printf("%lld\n",ans);
}
return ;
}
上一篇:UVa 1363 - Joseph's Problem(数论)


下一篇:UVA 1363 Joseph's Problem 找规律+推导 给定n,k;求k%[1,n]的和。