uva 1363 - Joseph's Problem(数论)

题目链接：uva 1363 - Joseph's Problem

题目大意：给定n，k，求∑i=1n(k%i).

解题思路：参考别人的，自己想了很久，详细题解

#include 
   
     #include 
    
      #include 
     
       #include 
      
        using namespace std; typedef long long ll; ll solve (ll n, ll k) { ll sum = 0; if (n > k) sum += (n-k) * k; ll a = sqrt(k+0.5), b = k / a; for (ll i = a; i > 1; i--) { ll s = k / i; ll e = k / (i-1); if (s > n) break; if (e > n) e = n; sum += ( (k%(s+1) + k%e) * (e - s) / 2); } for (ll i = 2; i <= b && i <= n; i++) sum += k%i; return sum; } int main () { ll n, k; while (scanf("%lld%lld", &n, &k) == 2) { printf("%lld\n", solve(n, k)); } return 0; }