ZOJ3558 How Many Sets III(公式题)

转载请注明出处： http://www.cnblogs.com/fraud/ ——by fraud

How Many Sets III

Time Limit: 2 Seconds Memory Limit: 65536 KB

Given a set S = {1, 2, ..., n}, your job is to count how many set T satisfies the following condition:

T is a subset of S
Elements in T can form an arithmetic progression in some order.

Input

There are multiple cases, each contains only one integer n ( 1 ≤ n ≤ 10⁹ ) in one line, process to the end of file.

Output

For each case, output an integer in a single line: the total number of set T that meets the requirmentin the description above, for the answer may be too large, just output it mod 100000007.

Sample Input

2

3

Sample Output

1

4

看到这种输出只和一个数有关的，而且还是整数，想都不想，先暴力求出前几项，然后oeis大法，查到公式后

a(n) = sum { i=1..n-1, j=1..floor((n-1)/i) } (n - i*j)

发现这个公式只是n^2的，于是我们需要优化其中的步骤，首先，对于第二维，我们很容易搞掉，那么对于第一维，我们发现其中有一个(n-1)/i，那么其实有很多是对应的，于是我们只需要枚举1到sqrt(n-1)即可。即对于每一个i，在公差在(n-1)/(i+1) + 1到(n-1)/i这个范围内是可求的，另外注意求一下其相对的情况，看上去比较轻松，然而我这种数学渣还是推了半个多小时才推出来的

 /**

  * code generated by JHelper

  * More info: https://github.com/AlexeyDmitriev/JHelper

  * @author xyiyy @https://github.com/xyiyy

  */

 #include <iostream>

 #include <fstream>

 //#####################

 //Author:fraud

 //Blog: http://www.cnblogs.com/fraud/

 //#####################

 //#pragma comment(linker, "/STACK:102400000,102400000")

 #include <iostream>

 #include <sstream>

 #include <ios>

 #include <iomanip>

 #include <functional>

 #include <algorithm>

 #include <vector>

 #include <string>

 #include <list>

 #include <queue>

 #include <deque>

 #include <stack>

 #include <set>

 #include <map>

 #include <cstdio>

 #include <cstdlib>

 #include <cmath>

 #include <cstring>

 #include <climits>

 #include <cctype>

 using namespace std;

 typedef long long ll;

 //

 // Created by xyiyy on 2015/8/5.

 //

 #ifndef ICPC_INV_HPP

 #define ICPC_INV_HPP

 typedef long long ll;

 void extgcd(ll a, ll b, ll &d, ll &x, ll &y) {

     if (!b) {

         d = a;

         x = ;

         y = ;

     }

     else {

         extgcd(b, a % b, d, y, x);

         y -= x * (a / b);

     }

 }

 ll inv(ll a, ll mod) {

     ll x, y, d;

     extgcd(a, mod, d, x, y);

     return d ==  ? (x % mod + mod) % mod : -;

 }

 #endif //ICPC_INV_HPP

 const ll mod = ;

 class TaskJ {

 public:

     void solve(std::istream &in, std::ostream &out) {

         ll n;

         while (in >> n) {

             ll ans = ;

             ll m = n - ;

             ll num = inv(, mod);

             for (ll i = ; i * i <= m; i++) {

                 ll r = m / i;

                 ll l = m / (i + ) + ;

                 if (l > r)continue;

                 ans += (n * i % mod * (r - l + ) % mod -

                         (1LL + i) * i % mod * num % mod * (l + r) % mod * (r - l + ) % mod * num % mod) % mod + mod;

                 ans %= mod;

                 if (i != r)ans += (n * r % mod - i * r % mod * (1LL + r) % mod * num % mod) % mod + mod;

                 ans %= mod;

             }

             out << ans << endl;

         }

     }

 };

 int main() {

     std::ios::sync_with_stdio(false);

     std::cin.tie();

     TaskJ solver;

     std::istream &in(std::cin);

     std::ostream &out(std::cout);

     solver.solve(in, out);

     return ;

 }

巴特西

ZOJ3558 How Many Sets III(公式题)

Input

Output

Sample Input

Sample Output

最新文章

热门文章