数学1-526互联

A.世纪之花

题目描述：

“丛林变得焦躁不安......”

世纪之花触手正在向丛林的各个角落蔓延。

现在丛林中已经有 x 个触手，每过一分钟世纪之花会长出一些新触手，新触手的数量等于当前触手数的最小质因子。

勇者准备出发，去击败世纪之花。勇者想要知道，再经过几分钟，世纪之花的触手数量就不小于 y 了呢？

输入格式：

第一行包含一个整数 T，表示数据组数。

接下来 T 行，每行两个正整数 x 和 y。

输出格式：

输出 T 行，每行一个整数表示答案。

样例输入：

4 2 23 9 20 5 100 6 89

样例输出：

11 5 46 42

数据规模：

$2≤X≤10，20≤Y≤10^9$

$设(x,y)=z，则x=k*z，若k%2==1，z=2，则不管加几个数都是奇数，从而得到(y-x+1)/2=世纪之花需要增长的时间，否则次数就变为z*(y-x-z+1)/2+1。$

x的范围是2~10。（括号里的为质因子）

x=2，（2）
x=3，3+3=6，（2）
x=4，（2）
x=5，5+5=10，（2）
x=6，（2）
x=7，7+7=14，（2）
x=8，（2）
x=9，9+3=12，（2）
x=10，（2）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int t;
 4 int main(){
 5     cin>>t;
 6     while(t--){
 7         int x,y;
 8         cin>>x>>y;
 9         int cnt=1;
10         if(x==2) x+=2;
11         else if(x==3) x+=3;
12         else if(x==4) x+=2;
13         else if(x==5) x+=5;
14         else if(x==6) x+=2;
15         else if(x==7) x+=7;
16         else if(x==8) x+=2;
17         else if(x==9) x+=3;
18         else if(x==10) x+=2;
19         cnt=(y-x+1)/2;
20         cout<<cnt+1<<endl;
21     }
22     return 0;
23 }

AC Code

B.参天大树

题目描述：

丛林中矗立着一棵参天大树，高度为 y。

大树 2~p 高度处，每个位置都有一只蚱蜢。

一只蚱蜢如果在 x 高度处，那么它可以跳到 2x、3x、4x、...... 等任意一个 x 的倍数处。

你想在 2~y 高度范围内，找到一个尽可能高且不会有任何蚂蚱能跳到的位置。

注意你和蚂蚱的位置都必须是整数，如果你找不到任何一个合法的位置的话，就输出-1。

输入格式：

第一行包含两个正整数 p 和 y。

输出格式：

输出一行一个整数表示答案。

样例输入：

3 6

样例输出：

样例输入：

3 4

样例输出：

-1

数据规模：

2 ≤ p ≤ y ≤ 10^9

需用知识点：n以内相邻两个质数的距离的最大值大概是在log^2*n左右（10^9大概是300）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define int long long
 4 int p,y;
 5 inline bool check(int x){
 6     for(int i=2;i<=sqrt(x);i++){
 7         if(x%i==0&&i>=2&&i<=p) return false;
 8     }
 9     return true;
10 }
11 inline void solve(){
12     cin>>p>>y;
13     int z=sqrt(y);
14     for(int i=y;i>=p+1;i--){
15         if(check(i)){
16             cout<<i<<"\n";
17             return;
18         }
19     }
20     cout<<"-1\n";
21 }
22 signed main(){
23     solve();
24     return 0;
25 }
26 
27 编译结果
28 compiled successfully
29 time: 4ms, memory: 3448kb, score: 100, status: Accepted
30 > test 1: time: 0ms, memory: 3384kb, points: 10, status: Accepted
31 > test 2: time: 1ms, memory: 3396kb, points: 10, status: Accepted
32 > test 3: time: 0ms, memory: 3400kb, points: 10, status: Accepted
33 > test 4: time: 1ms, memory: 3396kb, points: 10, status: Accepted
34 > test 5: time: 0ms, memory: 3396kb, points: 10, status: Accepted
35 > test 6: time: 0ms, memory: 3368kb, points: 10, status: Accepted
36 > test 7: time: 0ms, memory: 3432kb, points: 10, status: Accepted
37 > test 8: time: 1ms, memory: 3428kb, points: 10, status: Accepted
38 > test 9: time: 1ms, memory: 3448kb, points: 10, status: Accepted
39 > test 10: time: 0ms, memory: 3424kb, points: 10, status: Accepted

AC Code

C.小夏的大师旅程

时间限制: 1000ms

空间限制: 524288kB

题目描述

小夏已经踏上了成为最伟大的口袋妖怪大师的旅程。为了得到他的第一个口袋妖怪，他去了Zulu教授的实验室。由于小夏是Zulu教授最喜欢的学生，Zulu允许他从实验室里取出任意数量的口袋妖怪。但是Zulu警告他，每个小精灵都有一个力量值，例如k(k>1)个小精灵在一起，它们的力量值为{s1, s2, s3,…, sk}，如果gcd(s1, s2, s3,…, sk)=1(见GCD的定义注释)，它们之间就会互相打架。小夏作为一个聪明的人，不希望他的口袋妖怪互相斗争。然而，他也想最大化他从实验室里带走的神奇宝贝的数量。你能帮小夏找出他能带走的最大数量的口袋妖怪吗？注意：口袋妖怪不能与自己战斗。

输入格式

输入包含两行。第一行一个整数n(1<=n<=10^5)，表示实验室中的小精灵总数。第二行n个用空格隔开的整数，第i个整数代表第i个小精灵的力量值si(1<=si<=10^5)。

输出格式

一行包含一个整数，表示能拿走的小精灵数量最大值。

样例

Input 1

3 2 3 4

Output 1

Input 2

5 2 3 4 6 7

Output 2

数据范围

输入的小精灵总数n的范围是1到10^5，小精灵的力量值si的范围是1到10^5。

样例解释

对于样例1，小夏可以选择第2号和第4号小精灵，它们的力量值为{2, 4}，gcd(2, 4)=2，它们不会互相打架。所以最多可以拿走2个小精灵。对于样例2，小夏可以选择第1号、第3号和第4号小精灵，它们的力量值为{2, 4, 6}，gcd(2, 4, 6)=2，它们不会互相打架。所以最多可以拿走3个小精灵。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N=1e5+10;
 4 int ar[N],n;
 5 inline void check(int x){
 6     for(int i=2;i*i<=x;i++){
 7         if(x%i==0){
 8             ar[i]++;
 9             while(x%i==0) x/=i;
10         }
11     }
12     if(x>1) ar[x]++;
13 }
14 inline void solve(){
15     cin>>n;
16     for(int i=1,a;i<=n;i++){
17         cin>>a;
18         check(a);
19     }
20     int res=1;
21     for(int i=2;i<=N;i++){
22         res=max(res,ar[i]);
23     }
24     cout<<res<<"\n";
25 }
26 signed main(){
27     solve();
28     return 0;
29 }
30 
31 compiled successfully
32 time: 255ms, memory: 3840kb, score: 100, status: Accepted
33 > test 1: time: 42ms, memory: 3784kb, points: 10, status: Accepted
34 > test 2: time: 45ms, memory: 3780kb, points: 10, status: Accepted
35 > test 3: time: 34ms, memory: 3788kb, points: 10, status: Accepted
36 > test 4: time: 16ms, memory: 3788kb, points: 10, status: Accepted
37 > test 5: time: 36ms, memory: 3784kb, points: 10, status: Accepted
38 > test 6: time: 43ms, memory: 3780kb, points: 10, status: Accepted
39 > test 7: time: 0ms, memory: 3444kb, points: 10, status: Accepted
40 > test 8: time: 16ms, memory: 3788kb, points: 10, status: Accepted
41 > test 9: time: 1ms, memory: 3840kb, points: 10, status: Accepted
42 > test 10: time: 22ms, memory: 3756kb, points: 10, status: Accepted

AC Code