这个题很不错，卡了我半星期，再加上这个题没有题解，所以这次认真一些,因为不会LaTeX，这个题解写着挺吃力的。
题意
给定一个集合，这个集合的内容一定是{1,2,3,…,n}这个样子，要你求出这个集合的子集中，自成等差数列的有多少个。
举个例子，给出n=4，那么集合为{1,2,3,4},符合要求的子集有{1,2},{1,3},{1,4},{2,3},{2,4},{3,4},{1,2,3},{2,3,4},{1,2,3,4},一共有9个，输出9就可以了。
AC做法
特别感谢cos65535的题解（日文）。cos65535さん、ありがとうございます！
这里我来说明一下这个做法，对于一个给定的n，一共有1～n-1这些可能的公差，对于每个公差a，形成的等差数列最多有（(n-1)/a)＋1项，也就是最多可以扣掉(n-1)/a个公差。扣掉b个公差的话，可以最多形成n-ab个等差数列。
在这里举个例子来说明这个，给出一个n=8，求公差为3的情况，那么可以算出对于8，可以扣掉最多2个3保证等差数列的起点不出界。扣掉一个3的时候，形成2项的等差数列，这个等差数列的终点最大为8，也就是{5,8}，把这个数列整个减1，这样就得到{4,7}{3,6}{2,5},{1,4}，一共是5个（8-1*3），同样地扣掉两个3的时候，形成3项的等差数列，终点最大为8，即{2,5,8}，像刚才那样整体减1，得到{1,4,7}，一共是2个(8-2*3).2+5=7,这个就是公差3的时候可以组成的等差数列数目了。
这个方法写成公式很简单，就是
。
但是光有这个公式还不够，因为题目的数据范围是10^9,而上面介绍的那个做法是O(n^2)的时间复杂度，超时不可避啊。
优化需要两次，第一次是当公差一定时，我们可以用等差数列求和公式一次性求出来当前公差可以得到的当差数列数量。第二次是当我们使用完等差数列求和公式后，我们发现得到的式子中出现了n/a的形式，对于一定的n，a<=n,一共有sqrt(n)个n/a值（整数除法的特点），利用这一特点，我们可以只枚举1～sqrt(n-1)，我用这个范围枚举的是“最大可扣掉公差数目b”，对于给定的b，它适用于公差从(n-1)/b到(n-1)/(b+1)的情况，这里我们改造一下之前等差数列求和优化好的式子，再用一次等差数列求和。同时不要忘了我们的b值只枚举到了sqrt(n-1),每一次算出(n-1)/b其实就是对应的sqrt(n-1)以上的只对应一个公差的b值。
接下来上代码：
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
#include <cstdio> #include <iostream> #include <cmath> using namespace std; #define MODER 100000007 int main(){ long long n = 0; while (scanf(" %lld",&n) != EOF) { long long res = 0; long long b = 1; for (long long a = n-1; b <= sqrt(n-1);) { long long c = (n-1)/b - (n-1)/(b+1); //cout << a << '|' << b << "~" << c << endl; res += n*b*c-((a+a-c+1)*c/2)*b*(1+b)/2; if(!(a==b)) res += n*a-b*a*(1+a)/2; res %= MODER; b++; a = (n-1)/b; } printf("%lld\n",res); } return 0; } |
递推方法
感谢于济凡同学。
对于1～n这个集合的满足要求的子集数目，设定为f(n)，对于n－1这个数，小于等于它的数中可以整除它的数的数量设定为g(n)，我们有递推关系式f(n)=2f(n-1)-f(n-2)+g(n)
这里说明思路，{1,2,…,n}这个集合，我们可以看成是{1,…,n-1}这个集合组成的全部等差数列，加上{2,…,n}这个集合组成的全部等差数列，但是我们发现{2,…,n-1}这个集合的等差数列算了两次，我们要去掉一次，但是我们还是少了一种情况，就是以1开头，n结尾的等差数列数目，这个就是g(n)了。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 |
#include<iostream> #include<cmath> using namespace std; int f(int t) { int counter=0; for(int i=1;i<=t;i++) { if(t%i==0) counter++; } return counter; } int ans(int n) { if(n==1) return 0; else if(n==2) return 1; else return ans(n-1)*2%100000007-ans(n-2)%100000007+f(n-1)%100000007; } int main() { int m; while(cin>>m) { cout<<ans(m)<<endl; } } |
另一种求等差数列个数的方法
感谢铲神。
已知等差数列的公差、最后一项和首项，藉由等差数列通项公式，我们可以求出可用的等差数列数量。
其中
是公差
是最后一项
是首项，现在是n^2的时间复杂度，接下来优化为下面的形式，为n的时间复杂度，但是怎么弄成sqrt(n)的复杂度我实在想不出来了。。。
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include <cstdio> #include <iostream> #include <cmath> using namespace std; #define MODER 100000007 int main(){ long long n = 0; while (scanf(" %lld",&n) != EOF) { long long sum = 0; for (long long a = 1; a <= n; a++) { long long tmp =0; tmp += (1+n)*n/2; tmp -= (1+n%a)*(n%a)/2; tmp -= (1+a)*a/2*(n/a); cout << tmp; tmp /= a; cout << '~' << tmp << endl; tmp %= MODER; sum += tmp; sum %= MODER; } printf("%lld\n",sum%MODER); } return 0; } |
