首页 > 试题广场 >

小易的升级之路

[编程题]小易的升级之路
  • 热度指数：36591 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
小易经常沉迷于网络游戏.有一次,他在玩一个打怪升级的游戏,他的角色的初始能力值为 a.在接下来的一段时间内,他将会依次遇见n个怪物,每个怪物的防御力为b1,b2,b3...bn. 如果遇到的怪物防御力bi小于等于小易的当前能力值c,那么他就能轻松打败怪物,并 且使得自己的能力值增加bi;如果bi大于c,那他也能打败怪物,但他的能力值只能增加bi 与c的最大公约数.那么问题来了,在一系列的锻炼后,小易的最终能力值为多少?

输入描述:
对于每组数据,第一行是两个整数n(1≤n<100000)表示怪物的数量和a表示小易的初始能力值.
然后输入n行，每行整数,b1,b2...bn(1≤bi≤n)表示每个怪物的防御力


输出描述:
对于每组数据,输出一行.每行仅包含一个整数,表示小易的最终能力值
示例1

输入

3 50
50 105 200
5 20
30 20 15 40 100

输出

110
205
算法知识视频讲解
查看答案及解析
添加回答
推荐
小小头像 小小 
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
using namespace std;
int gcd(int a,int b){
	int tmp;
	while(b){
		tmp = b; b = a % b ; a = tmp;
	}
	return a;
}
int main(){
	int n,a;
	while(scanf("%d%d",&n,&a) != EOF){
		for(int i = 0,x;i < n;++ i){
			scanf("%d",&x);
			if(x <= a) a += x;
			else a += gcd(x,a);
		}
		printf("%d\n",a);
	}
	return 0;
}
编辑于 2016-03-01 14:24:00 回复(14)
smartada头像 smartada 
#include <stdio.h>
int gcd (int m,int n){
    if (n == 0)
        return m;
    else
        return gcd(n,m%n);
}
int main() {
    int n,a,num;
    while(~scanf("%d %d",&n,&a)){
        for (int i=0;i<n;i++){
            scanf("%d",&num);
            if (num <= a)
                a+=num;
            else
                a+=gcd(num,a);
        }
        printf("%d\n",a);
    }
    return 0;
}

发表于 2016-03-15 23:08:13 回复(0)
闯关东俊哥头像 闯关东俊哥 
import java.util.Scanner;

public class Main {
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		while (scanner.hasNextInt()) {
			Integer monsterCount = scanner.nextInt();
			Integer initialPower = scanner.nextInt();

			Integer currentPower = initialPower;
			for (int i = 0; i < monsterCount; i++) {
				Integer defensivePower = scanner.nextInt();
				if (defensivePower <= currentPower) {
					currentPower += defensivePower;
				} else {
					currentPower += Main.getGreatestCommonDivisor(currentPower, defensivePower);
				}
			}
			System.out.println(currentPower);
		}
		scanner.close();
	}

	private static Integer getGreatestCommonDivisor(Integer firstNum, Integer secondNum) {
		if (firstNum < secondNum) {
			int temp;
			temp = firstNum;
			firstNum = secondNum;
			secondNum = temp;
		}
		if (0 == secondNum) {
			return firstNum;
		}
		return Main.getGreatestCommonDivisor(secondNum, firstNum % secondNum);
	}

}

发表于 2015-11-26 09:19:21 回复(0)
C/C++
cycleof头像 cycleof 
#include<iostream>
using namespace std;
int GCD(int a,int b){//辗转相除法，后附证明
    int temp;
    while(b){
        temp = b; b = a%b; a = temp;
    }
    return (a);
}
int main(){
    int n,c;
    while( cin >> n >> c ){
        int i,temp;
        for(i=0;i<n;i++){
            cin >> temp;
            if( c >= temp )
                c += temp;
            else
                c += GCD(c,temp);
        }
        cout << c <<endl;
    }
}
/*辗转相除法证明：
1.证明有相同公因子：用gcd（a，b） = c 表示a，b的最大公约数为c，设 a = ce， b = cf； 
  a/b = d 余数为 r。 则有 a = bd + r 则有ce = cfd + r 则有 r = （e-fd）c ，b = cf。
  由此知 （b，r） 也有 c 的公因子，而 c 为a，b的最大公因子。
2.证明该公因子最大，即证明（e-fd） 和 f 互质。 假设不互质 即存在着某g>1。
  使得 e-fd = gh ,f = gj 。a = ce = c（fd+gh） = c（gjd + gh） = cg（jd+h），b = cgj。
  则（a，b） 有大于 c 的公因子 cg ，和已知矛盾，故假设错误。互质成立！c公因子最大。
3.由1,2知，a，b的最大公因子c。恰为b，r的最大公因子。 则gcd（a，b） = gcd（b，r）。辗转相除法成立！*/
编辑于 2017-07-01 23:30:11 回复(1)
航棍头像 航棍 
import java.util.Scanner;

public class Main {

	public static void main(String[] args) {
		System.out.println("输入怪的数量: ");
		Scanner in = new Scanner(System.in);
		int gNum = in.nextInt();
		if(gNum<=0){
			System.out.println("怪物数不能少于0个");
			System.exit(0);
		}
		int[] array = new int[gNum];
		System.out.println("输入小易初始能力值: ");
		int powNum = in.nextInt();
		if(gNum<1||gNum>=100000){
			System.out.println("生命值输入错误");
			System.exit(0);
		}
		System.out.println("输入怪物的能力值:： ");
		for(int i=0;i<gNum;i++){
			array[i] = in.nextInt();
			if(array[i]<=0||array[i]>=10000){
				System.out.println("怪物生命值输入错误");
				System.exit(0);
			}
		}
		
		for(int i=0;i<gNum;i++){
			powNum = powNum + fight(powNum,array[i]);
		}
		System.out.println("最终生命值为："+ powNum);
		System.exit(0); 

	}
	
	public static int fight(int i, int j){
			if(i>=j) {
				return j;
			}
			else
				return maxYS(i,j);
	}	
	
	public static int maxYS(int i,int j){
	      while (i%j != 0) {   
	    	  	int temp = i%j;   
	            i = j;   
	            j = temp;   
	        } 
	      return j;
	}

}

编辑于 2015-11-26 13:06:11 回复(9)
TPU-Lee头像 TPU-Lee
#include<iostream>
using namespace std;
 
intgcd(intm,intn)
{
    if(m<n)
        returngcd(n,m);
    if(n==0)
        returnm;
    else
        returngcd(n,m%n);
      //  return n == 0 ? m : gcd(n,m%n);
}
  
intmain()
{
    intn,a;
    inttemp;
    while(cin>>n>>a){
        for(inti = 0;i < n;i++){
            cin>>temp;
            if(a >= temp)
                a += temp;
            else
                a += gcd(temp,a);
        }
        cout<<a<<endl;
    }
    return0;
}
发表于 2015-12-18 17:10:30 回复(0)
铅笔头宝宝头像 铅笔头宝宝

import java.util.Scanner;

public class Main {
 public static void main(String[] args) {
  Scanner input = new Scanner(System.in);
  // System.out.println("请输入怪物数量和小易的初始能力值，以空格分隔：");
  while (input.hasNext()) {
   // 怪物的数量
   int n = input.nextInt();
   // 小易初始能力值
   int ability = input.nextInt();
   // 定义怪物数组
   int[] monsters = new int[n];
   // 输入每个怪物的防御力
   for (int i = 0; i < n; i++) {
    monsters[i] = input.nextInt();
   }
   // 小易遇怪
   for (int i = 0; i < n; i++) {
    if (ability > monsters[i] || ability == monsters[i]) {
     ability = ability + monsters[i];
    } else {
     ability = ability + GCF(ability, monsters[i]);
    }
   }
   // 打完怪了，输出结果
   System.out.println(ability);
  }
 }

 public static int GCF(int A,int B){
  if(B==0){
   return A;
  }else
   return GCF(B,A%B);
 }
}

发表于 2016-03-12 09:41:35 回复(4)
Java
pein531头像 pein531
直接模拟打怪过程就可以了，不过很坑，示例里面怪物的防御力是一行输入并用空格分隔的，但提交之后根本不是这样，是换行输入的！ 
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String line;
        while((line = br.readLine()) != null){
            String[] params = line.split(" ");
            int n = Integer.parseInt(params[0]);
            int a = Integer.parseInt(params[1]);
            for(int i = 0; i < n; i++){
                int b = Integer.parseInt(br.readLine());
                if(a >= b){
                    a += b;
                }else{
                    a += gcd(b, a);
                }
            }
            System.out.println(a);
        }
    }
    
    private static int gcd(int n, int m) {
        if(m == 0){
            return n;
        }
        return gcd(m, n % m);
    }
}

发表于 2022-01-13 11:21:57 回复(0)
Java
小熊歪泥头像 小熊歪泥 
import java.util.*;
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            int n = sc.nextInt();
            int a = sc.nextInt();
            int[] nums = new int[n];
            for(int i = 0;i < n;i++){
                nums[i] = sc.nextInt();
                if(nums[i] <= a) a += nums[i];
                else a += method(a,nums[i]);
            }
            System.out.println(a);
        }
    }
    
    private static int method(int a ,int b){
        //辗转相除法
        while(b != 0){
            int r = a % b;
            a = b;
            b = r;
        }
        return a;
    }
}

发表于 2021-08-19 22:59:32 回复(0)
峰峰的牛客头像 峰峰的牛客 
//很详细
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        while(sc.hasNext()){
            int a=sc.nextInt(); //a表示怪物的数量
            int b=sc.nextInt(); //b表示小易的初始化能力
            int[] arr=new int[a];
            for(int i=0;i<a;i++){
                arr[i]=sc.nextInt(); //用数组arr把每个怪物的防御力记录下来
            }
            for(int i=0;i<arr.length;i++){
                if(b>=arr[i]){//如果能力大于等于怪物防御力，则直接加
                    b+=arr[i];
                }else {
                    b+=maxCommon1(arr[i],b);//如果能力小于怪物防御力，则直接加上它们的最大公约数
                   // b+=maxCommon2(arr[i],b);
                   // b+=maxCommon3(arr[i],b);
                }
            }
            System.out.println(b);
        }
    }
    //求最大公约数方法1：穷举法
    private static int maxCommon1(int a,int b){
        if(a<b){ //如果a<b，先把ab交换，方便以后操作
            int tmp=a;
            a=b;
            b=tmp;
        }
        //如果b能直接整除a，说明b是它们的最大公约数
        if(a%b==0){
            return b;
        }
        //否则从小的开始依次整除，当a和b同时能整除那个数的时候说明就是它们的最大公约数
        for(int i=b-1;i>1;i--){
            if(a%i==0&&b%i==0){
                return i;
            }
        }
        return 1; //说明除完还没有找到，只能返回1
    }
    //求最大公约数方法2：辗转相减法
    /**两个数，相等时，最大公约数为他们其中任意一个。
       不相等时，用大数减小数。得到的差和之前的那个小数再次相减，直到两个数相等，这两个中，任意一个都是最大公约数。
     */
    private static int maxCommon2(int a,int b){
        while((a-b)!=0){
            if(a>b){
                a=a-b;
            }else {
                b=b-a;
            }
        }
        return b;
    }
    //求最大公约数方法3：辗转相除法

    /**
     * 用大数对小数求余，若余数为0，则除数为最大公约数。
     * 若余数不为0，将此余数作为除数，小数作为被除数，重新求余，直到余数为0为止。
     * 此时的最大公约数为余数。例如：27和6.  27%6=3,6%3=0.所以最大公约数为3.
     */
    private static int maxCommon3(int a,int b){
        if(a<b){ //如果a<b，先把ab交换，方便以后操作
            int tmp=a;
            a=b;
            b=tmp;
        }
        int n=a%b;
        while(a%b!=0){
            a=b;
            b=n;
            n=a%b;
        }
        return b;
    }
}

发表于 2019-12-04 09:13:15 回复(0)
skrskr66头像 skrskr66 
#include <iostream>
#include <vector>
using namespace std;

int get_num(int num1,int num2)
{
    while(num2)
    {
        int tmp = num2;
        num2 = num1 % num2;
        num1 = tmp;
    }
    return num1;
}

int main()
{
    int num = 0,val = 0;
    while(cin>>num>>val)
    {
        vector<int> v(num,0);
        for(size_t i = 0;i<num;i++)
        {
            cin>>v[i];
        }
        for(int j = 0;j < num;j++)
        {
            if(val >= v[j])
            {
                val += v[j];
            }
            else
            {
                int temp = get_num(val,v[j]);
                val +=temp;
            }
        }
        cout<<val<<endl;
    }
    return 0;
}

发表于 2019-06-13 12:23:08 回复(0)
想风一样自由头像 想风一样自由 
//单纯的求最大公约数，辗转相除法
#include<iostream>
using namespace std;
int gcb(int a, int b)
{
    if(b == 0)
        return a;
    return gcb(b, a%b);
}

int main()
{
    int n,cap;
    while(cin>>n>>cap){
        for(int i=0; i<n; i++){
            int tmp;
            cin>>tmp;
            if(tmp <= cap){
                cap += tmp;
            }else if(tmp > cap){
                cap += gcb(tmp, cap);
            }
        }
        cout<<cap<<"\n";
    }
    
    return 0;
}

发表于 2017-09-16 16:54:03 回复(0)
蓝魔4头像 蓝魔4 
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int gcd(int num1,int num2)
{
    int Min=min(num1,num2);
    for(int i=Min;i>=1;i--)
    {
        if(num1%i==0&&num2%i==0)
        {
            Min=i;
            break;
        }
    }
    return Min;
}
int level(int index,int &a,vector<int> &ghost,int n)
{
    if(index==n)
        return a;
    if(ghost[index]<=a)
        a+=ghost[index];
    else
    	a+=gcd(a,ghost[index]);
    return level(++index,a,ghost,n);
}
int main()
{
    int n,a;
    while(cin>>n>>a)
    {
        vector<int> ghost(n);
        for(int i=0;i<n;i++)
            cin>>ghost[i];
        cout<<level(0,a,ghost,n)<<endl;
    }
    return 0;
}

发表于 2017-06-30 19:46:15 回复(0)
todo-v头像 todo-v 
#include <iostream>
#include <vector>

using namespace std;

int gcd(int a,int b){
    if( b == 0 ){
        return a;
    }
    return gcd(b,a%b);
}

int main() {
	//code
	int n,a,in,get_power = 0;
	vector<int> power_;
	while(cin >> n >> a){
	    power_.clear();
	    get_power = a;
	    if( n == 0 ){
	        cout<<a<<endl;
	        continue;
	    }
	    for( int i = 0 ;i < n ; i ++ ){
	        cin>>in;
	        power_.push_back( in );
	    }
	    for( int i = 0; i < n ;i ++ ){
	        if( get_power >= power_[i] ){
	            get_power += power_[i];
	        }else{
	            get_power += gcd(get_power,power_[i]);
	        }
	    }
	    cout<<get_power<<endl;
	}
	return 0;
}

发表于 2017-04-13 11:19:22 回复(0)
乐天知命头像 乐天知命 
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		while (in.hasNext()) {
			int n = in.nextInt();
			int a = in.nextInt();
			int[] b = new int[n];
			for (int i = 0; i < n; i++) {
				b[i] = in.nextInt();
			}
			int ans = getResult(a, b);
			System.out.println(ans);
		}
	}
	private static int getResult(int a, int[] b) {
		// TODO Auto-generated method stub
		// Arrays.sort(b); 注意：此处不能排序！
		for (int i = 0; i < b.length; i++) {
			if (a > b[i]) {
				a += b[i];
			} else {
				a += maxCommonDivisor(a, b[i]);
			}
		}
		return a;
	}
	public static int maxCommonDivisor(int m, int n) {
		if (m < n) {// 保证m>n,若m<n,则进行数据交换  
            int temp = m;  
            m = n;  
            n = temp;  
        }  
        while (m % n != 0) {// 在余数不能为0时,进行循环  
            int temp = m % n;  
            m = n;  
            n = temp;  
        }  
        return n;// 返回最大公约数  
	}
}

编辑于 2017-03-25 13:20:55 回复(0)
冉承祥头像 冉承祥 
#include<iostream>
#include<vector>
using namespace std;
int fun(int a,int b)
  { if(a==1||b==1) return 1;
    int i=2,j;
    while(i<=a&&i<=b)
      { if((a%i==0)&&(b%i==0)) j=i;
        i++;  
      }
    return j;
  }
int main()
{   int n,a,s,i,j;
    int *b;
    while(cin>>n>>a)
     { b=new int[n];
       j=0;s=a;
       while(j<n)
        {cin>>b[j++];}
       for(i=0;i<n;i++)
         { if(s>=b[i]) s+=b[i];
           else s+=fun(b[i],s);  
         }
       cout<<s<<endl;
       delete[] b;
     }
    return 0;
}

发表于 2016-10-16 13:30:39 回复(0)
fight灬奋斗头像 fight灬奋斗 
#include <iostream>
#include <vector>
using namespace std;
int count(int a,int b){
    while(a%b){
        int temp=b;
        b=a%b;
        a=temp;
    }
    return b;
}
int main(){
    int N,a,b;
    while(cin>>N>>a){
       for(int i=0;i<N&&cin>>b;i++)
            if(b<=a)
               a+=b;
        	else
                a+=count(a,b);
       cout<<a<<endl;          
    }
    return 0;
}

发表于 2016-09-07 14:53:15 回复(0)
会呼吸旳痛头像 会呼吸旳痛 
#include <iostream>
#include <vector>
using namespace std;

typedef long long llint;
llint gcd(llint a, llint b)
{
	if(a%b==0)return b;
	return gcd(b,a%b);
}

int main()
{
	int n;
	llint a;
	while(cin>>n>>a)
	{
		while(n--)
		{
			llint b;
			cin>>b;
			if(a>=b)a+=b;
			else a += gcd(a,b);
		}
		cout<<a<<endl;
	}
	return 0;
}

发表于 2016-08-18 11:36:34 回复(0)
赞一下头像 赞一下 
//    主要是求解最大公约数，其它就是注意输入输出要求
#include<iostream>
#include<vector>

using namespace std;

int GreatCommonDivision( int a, int b )
    {
    int max = 0, min = 0, r = 0;
    a >= b ? ( max = a, min = b ) : ( max = b, min = a );
    r = b;
    while ( r != 0 )
        {
        r = a % b;
        a = b;
        b = r;
    }
    return a;
}

int main(void)
    {
    int num = 0, initValue = 0, defence = 0;
    vector<int> ivec;
    while ( cin >> num >> initValue )
        {
        while ( num-- != 0 && cin >> defence )
            ivec.push_back( defence );
        for ( auto c : ivec )
            {
            if ( initValue >= c )
                initValue += c;
            else
               initValue += GreatCommonDivision( initValue, c ) ;
        }
        cout << initValue << endl;
        ivec.clear();
    }
    return 0;
}

编辑于 2016-08-16 21:40:26 回复(0)
C/C++
吭哧吭哧埋头干头像 吭哧吭哧埋头干 
#include<stdio.h>
int get(int a,int b){//最大公约数 
	int n=a>b?a:b;
	int m=a<b?a:b;
	int p=n%m;
	while(p){
		n=m;
		m=p;
		p=n%m;
	}
	return m;
    
    
}
int main(){
    int n,a,b,i;
	while(scanf("%d %d",&n,&a)!=EOF){
		for(i=0;i<n;i++){
			scanf("%d",&b);
			if(b<=a){
				a+=b;
			}else{
				a+=get(a,b);
			}
		}
		printf("%d\n",a);
	}
    return 0;
}

发表于 2016-08-11 15:13:03 回复(0)
Shield_W头像 Shield_W 

	import java.util.*;





	public class Main{





	    public static void main(String[] args) {





	        Scanner sc = new Scanner(System.in);





	        while(sc.hasNext()) {





	            intn = sc.nextInt();





	            inta = sc.nextInt();





	            int[] b = new int[n];





	            for(inti = 0; i < n; i++) {





	                b[i] = sc.nextInt();





	                if(b[i] > a) {





	                    a += gcd(b[i], a);





	                } else{





	                    a += b[i];





	                }





	            }





	            System.out.println(a);





	        }





	    }





	    public static int gcd(int m, int n) {





	        return n == 0? m : gcd(n, m % n);





	    }

编辑于 2016-08-01 12:16:17 回复(0)
提交观点

问题信息

模拟 数学 递归
来自：网易2016校招研发工...
难度：
215条回答 39884浏览

热门推荐

通过挑战的用户

查看代码

相关试题

小易的升级之路

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号