HDU 数论二 1002Ice Rain

参考博客 https://blog.csdn.net/acm_cxq/article/details/51627935

题目地址HDU 2620

题目大意 ：给你 一个 n，k求 的值

题目思路：n,k的范围1 <= n, k <= 10^{9 直接枚举肯定超时}

                   ^{利用mod 的本身定义 kmod i=k-[k/i]*i}

 ^{=n*k-（1*[k/1]+2*[k/2]+....+n*[k/n]）}

^{[k/i] 是取整的符号，所以说[k/i]到[k/n] 可能会有很多值相等的区间}

^{设d=[k/i]   j=[k/d]  所以在[i,j]这个区间里面 【k/i】都等于d这样子就减少了很多枚举 下一次可以直接跳到 i=j+1}

还可以证明这个 j一定是最后的一个 是的【k%j】=d

  我们假设k/(j+1)=d，那么有d(j+1)<=k  而根据k/d=j可以推出k-(d*j)<d即k<d*(j+1)

本题 注意点n,k数值很大所以要使用long long 类型

对于long long 类型 使用scanf("%lld")    printf("%lld")

#include<iostream> using namespace std; int main() { long long n,k; long long ans; while(cin>>n>>k) { ans=n*k; if(n>k) n=k;//当 n>k时 [k/n]=0 for(int i=1;i<=n;) { long long d=k/i; long long j=k/d; if(j>n) j=n; ans=ans-d*(i+j)*(j-i+1)/2; i=j+1; } cout<<ans<<endl; } return 0; }