UVA1583 - Digit Generator

  

   

    

     

    
    

     

      //UVA1583 - Digit Generator
     
    
   

    

     

    
    

     

      //題目:数x加上它各个位数之和得到一个y，x为y的最小生成元。求一个数的最小生成元
     
    
   

    

     

    
    

     

      //分析：打表，查表
     
    
   

    

     

    
    

     

      #include<stdio.h>
     
    
   

    

     

    
    

     

      #define MAXN 100005
     
    
   

    

     

    
    

     

      int ans[MAXN] = {0};
     
    
   

    

     

    
    

     

      int main(){
     
    
   

    

     

    
    

     
	int T, n;
     
    
   

    

     

    
    

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

    

     

    
    

     
		int x = i, y = i;
     
    
   

    

     

    
    

     
		while(x>0){ y += x%10; x /= 10;}
     
    
   

    

     

    
    

     
		//*1.该数的大小加上它本身已经越界即超过100000
     
    
   

    

     

    
    

     
		//*2.用更小的生成元替换原来的生成元，得到最小生成元
     
    
   

    

     

    
    

     
		if(ans[y] == 0 || i < ans[y])ans[y] = i;	
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	scanf("%d",&T);
     
    
   

    

     

    
    

     
	while(T--){
     
    
   

    

     

    
    

     
		scanf("%d",&n);
     
    
   

    

     

    
    

     
		printf("%d\n",ans[n]);
     
    
   

    

     

    
    

     

      	}
     
    
   

    

     

    
    

     
	return 0;
     
    
   

    

     

    
    

     

      }
     
    
  
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/54838257