codeforces Soldier and Number Game(dp+素数筛选)

简介:
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
                              D. Soldier and Number Game
                          time limit per test3 seconds
                          memory limit per test256 megabytes
                          inputstandard input
                          outputstandard output
Two soldiers are playing a game. At the beginning first of them chooses a positive integer n and gives it to the second soldier. Then the second one tries to make maximum possible number of rounds. Each round consists of choosing a positive integer x > 1, such that n is divisible by x and replacing n with n / x. When n becomes equal to 1 and there is no more possible valid moves the game is over and the score of the second soldier is equal to the number of rounds he performed.
 
To make the game more interesting, first soldier chooses n of form a! / b! for some positive integer a and b (a ≥ b). Here by k! we denote the factorial of k that is defined as a product of all positive integers not large than k.
 
What is the maximum possible score of the second soldier?
 
Input
First line of input consists of single integer t (1 ≤ t ≤ 1 000 000) denoting number of games soldiers play.
 
Then follow t lines, each contains pair of integers a and b (1 ≤ b ≤ a ≤ 5 000 000) defining the value of n for a game.
 
Output
For each game output a maximum score that the second soldier can get.
 
Sample test(s)
input
2
3 1
6 3
output
2
5

  

复制代码
/*
    dp求解 n!的质因子个数。 
    1.首先利用素数筛选法求出素数的集合
    2.dp[i] = dp[i/prime[j]]+1, i%prime[j]==0; prime[j]是第一个能整除i的数 
*/
#include<iostream> 
#include<cstring>
#include<cstdio>
#include<algorithm>
#define N 5000005
using namespace std;

int prime[N];
bool isprime[N];
int dp[N];
void init(){
    int top = 0;
    for(int i=2; i<N; ++i){
        if(!isprime[i])
            prime[top++] = i;
        for(int j=0; j<top && i*prime[j]<N; ++j){//素数筛选 
            isprime[i*prime[j]] = true;
            if(i%prime[j] == 0)
                break;
        }
    }
    for(int i=2; i<N; ++i){
        if(!isprime[i])
            dp[i] = 1;
        else{
            for(int j=0; j<top; ++j)
                if(i%prime[j]==0){
                    dp[i] = dp[i/prime[j]] + 1;
                    break;
                }
        }
    }
    for(int i=2; i<N; ++i)//前n个数的质因数个数的和 
        dp[i]+=dp[i-1];
}
 
int main(){
    int t;
    scanf("%d", &t);
    init();
    while(t--){
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", dp[a] - dp[b]);
    }
    return 0; 
} 
复制代码









本文转自 小眼儿 博客园博客,原文链接:http://www.cnblogs.com/hujunzheng/p/4529072.html,如需转载请自行联系原作者
目录
相关文章
|
小程序 C语言
【入门级C语言程序 -- 猜数字】Guess Number Game
【入门级C语言程序 -- 猜数字】Guess Number Game
223 0
【入门级C语言程序 -- 猜数字】Guess Number Game
|
测试技术
优先队列+模拟-Fox and Number Game
codeforces-Fox and Number Game 题目地址:http://codeforces.com/contest/389/problem/ATime Limit: 1000msFox Ciel is playing a game with numbers now. Ciel has n positive integers: x1, x2, ..., xn. She
1149 0
|
6月前
|
算法
Leetcode 313. Super Ugly Number
题目翻译成中文是『超级丑数』,啥叫丑数?丑数就是素因子只有2,3,5的数,7 14 21不是丑数,因为他们都有7这个素数。 这里的超级丑数只是对丑数的一个扩展,超级丑数的素因子不再仅限于2 3 5,而是由题目给定一个素数数组。与朴素丑数算法相比,只是将素因子变了而已,解法还是和朴素丑数一致的。
66 1
|
9天前
|
存储 算法
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
【LeetCode力扣】单调栈解决Next Greater Number(下一个更大值)问题
8 0
|
6月前
|
存储
Leetcode Single Number II (面试题推荐)
给你一个整数数组,每个元素出现了三次,但只有一个元素出现了一次,让你找出这个数,要求线性的时间复杂度,不使用额外空间。
22 0
LeetCode 136. 只出现一次的数字 Single Number
LeetCode 136. 只出现一次的数字 Single Number
LeetCode contest 177 5169. 日期之间隔几天 Number of Days Between Two Dates
LeetCode contest 177 5169. 日期之间隔几天 Number of Days Between Two Dates
|
算法
LeetCode 414. Third Maximum Number
给定一个非空数组,返回此数组中第三大的数。如果不存在,则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
68 0
LeetCode 414. Third Maximum Number