本文主要是介绍J - Joseph’s Problem 找规律，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
给出n k
当 i 属于 1~n 时 ，求解 n% i 的和
n 和 k 的范围都是 1 到 十的九次方
普通的计算当然会超时
我们先通过打表几个数来看看
下面的括号表示当余数为0的时候 i 为多少
n = k =90 的时候
0 (1)0 (2)0 (3)2 0 (5)0 (6)6 2 0 (9)0 (10)
2 6 12 6 0 (15)10 5 0 (18)14 10
6 2 21 18 15 12 9 6 3 0 (30)
28 26 24 22 20 18 16 14 12 10
8 6 4 2 0 (45)44 43 42 41 40
39 38 37 36 35 34 33 32 31 30
29 28 27 26 25 24 23 22 21 20
19 18 17 16 15 14 13 12 11 10
9 8 7 6 5 4 3 2 1 0 (90)
n = k =91 的时候
**************************************
0 (1)1 1 3 1 1 0 (7)3 1 1
3 7 0 (13)7 1 11 6 1 15 11
7 3 22 19 16 13 10 7 4 1
29 27 25 23 21 19 17 15 13 11
9 7 5 3 1 45 44 43 42 41
40 39 38 37 36 35 34 33 32 31
30 29 28 27 26 25 24 23 22 21
20 19 18 17 16 15 14 13 12 11
10 9 8 7 6 5 4 3 2 1
0 (91)
**************************************
n = k =92 的时候
0 (1)0 (2)2 0 (4)2 2 1 4 2 2
4 8 1 8 2 12 7 2 16 12
8 4 0 (23)20 17 14 11 8 5 2
30 28 26 24 22 20 18 16 14 12
10 8 6 4 2 0 (46)45 44 43 42
41 40 39 38 37 36 35 34 33 32
31 30 29 28 27 26 25 24 23 22
21 20 19 18 17 16 15 14 13 12
11 10 9 8 7 6 5 4 3 2
1 0 (92)
**************************************
n = k =93 的时候
0 (1)1 0 (3)1 3 3 2 5 3 3
5 9 2 9 3 13 8 3 17 13
9 5 1 21 18 15 12 9 6 3
0 (31)29 27 25 23 21 19 17 15 13
11 9 7 5 3 1 46 45 44 43
42 41 40 39 38 37 36 35 34 33
32 31 30 29 28 27 26 25 24 23
22 21 20 19 18 17 16 15 14 13
12 11 10 9 8 7 6 5 4 3
2 1 0 (93)
**************************************
容易发现，都是等差数列，只是前面的比较难以发现
那么我们从后往前看
后面是等差为1的等差数列
再前面一个就是等差为2的等差数列
再前面一个就是等差为3的等差数列
并且上叙 1 2 3都是 n/i 得到的
最后要注意下都用长整型的防止溢出
并且计算等差数列的项的时候不能超出n
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;#define LL long longint main()
{LL sum;LL n,k;//freopen("in.txt","r",stdin);freopen("joseph.in","r",stdin);freopen("joseph.out","w",stdout);while(scanf("%lld%lld",&n,&k)!=EOF){sum=0;LL a1,d,x;for(LL i=2;i<=n;i+=x){a1=k%i;d=k/i;if(d==0){sum+=a1*(n-i+1);break;}x=a1/d+1;x=min(x,n-i+1);sum+=x*a1-x*(x-1)*d/2;}printf("%lld\n",sum);}return 0;
}
这篇关于J - Joseph’s Problem 找规律的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
