数学+DP Codeforces Round #304 (Div. 2) D. Soldier and Number Game

时间：2024-01-17 15:22:14

题目传送门

 /*

    题意：这题就是求b+1到a的因子个数和。

    数学+DP：a[i]保存i的最小因子，dp[i] = dp[i/a[i]] +１;再来一个前缀和

 */

 /************************************************

 Author        :Running_Time

 Created Time  :2015-8-1 14:08:34

 File Name     :B.cpp

  *************************************************/

 #include <cstdio>

 #include <algorithm>

 #include <iostream>

 #include <sstream>

 #include <cstring>

 #include <cmath>

 #include <string>

 #include <vector>

 #include <queue>

 #include <deque>

 #include <stack>

 #include <list>

 #include <map>

 #include <set>

 #include <bitset>

 #include <cstdlib>

 #include <ctime>

 using namespace std;

 typedef long long ll;

 const int MAXN = 5e6 + ;

 const int INF = 0x3f3f3f3f;

 const int MOD = 1e9 + ;

 int cnt[MAXN];

 int a[MAXN];

 bool is_prime[MAXN];

 int prime[MAXN/];

 ll dp[MAXN];

 ll sum[MAXN];

 void solve(void)    {

     memset (is_prime, true, sizeof (is_prime));

     for (int i=; i<=; ++i)  a[i] = i;

     int tot = ;

     for (int i=; i<=; ++i)  {

         if (is_prime[i])    prime[++tot] = i;

         for (int j=; j<=tot && i*prime[j]<=; ++j)   {

             int tmp = i * prime[j];

             is_prime[tmp] = false;

             if (a[tmp] > prime[j])  a[tmp] = prime[j];

             if (i % prime[j] == )  break;

         }

     }

     dp[] = ;

     for (int i=; i<=; ++i)  {

         dp[i] = dp[i/a[i]] + ;

     }

     for (int i=; i<=; ++i)  {

         sum[i] = sum[i-] + dp[i];

     }

 }

 int main(void)    {       //Codeforces Round #304 (Div. 2) D. Soldier and Number Game

     solve ();

     int T;  scanf ("%d", &T);

     while (T--) {

         int l, r;   scanf ("%d%d", &r, &l);

         if (l == r) {

             puts (""); continue;

         }

         printf ("%I64d\n", sum[r] - sum[l]);

     }

     return ;

 }

相关文章