UVa1583 最小生成元
在刘汝佳老师的《算法竞赛入门经典（第2版）》52页例题3-5中看到此题，发现此题并不需要枚举太多，实际上只需要枚举很少的值即可。
原题内容如下
例题 3-5  生成元 （Digit Generator, ACM/ICPC Seoul 2005, UVa1583）

如果x加上x的各个数字之和得到y，就说x是y的生成元。给出n(1<=n<=100000)，求最小生成元。无解输出0。例如，n=216，121，2005时的解分别为198，0，1979。
分析
由于每个数位的数字最大为9，那么m位数字之和最大为9m。假设y是m位数，x的位数必然<=m，假设x也是与y相同的m位数，那么x与y的最大差值为9m，由x最小值y-9m开始逐个尝试，最多不超过9*m次即可找到最小x值。根据本题的数据上限，枚举最多不超过54次x值即可。
以下为代码
#include <stdio.h>
#include <string.h>
#include <ctype.h>
#include <time.h>

int main()
{
	int n, x, y, m=0, sum, got;
	scanf("%d", &n);
	y = n;
	while(y>0) // 求出y的位数m
	{
		y /= 10;
		m++;
	}
	
	got = 0; // 是否得到解
	if(n-9*m<=0) x=1;// 处理n-9*m负值的情况
	else x=n-9*m;
	for(; x<n; x++)
	{
		sum = 0;
		int temp = x;
		while(temp>0) // 得到x各个数位之和sum
		{
			sum += temp%10;
			temp /= 10;
		}
		if(x+sum==n){
			got = 1;
			break;
		}
	}
	if(got==0) printf("%d\n", 0);
	else printf("%d\n", x);
	return 0; // 返回
}

本文为原创，如需转载，请注明作者和出处，谢谢！
最近看了有道出的几个复赛题，觉得很好玩，现给出Java版的答案。先看看提干部分
  如果一个数字十进制表达时，不存在连续两位数字相等，则称之为“不重复数”。例如，105，1234和12121都是“不重复数”，而11，100和 1225不算。给定一个long类型数字A，返回大于A的最小“不重复数”。 下面是几个测试用例，我又加了几个
Examples:
0) 54
 returns： 56
 大于54的最小数字是55，但55不是“不重复数”。下一个数字是56，它满足条件。
1) 10
 returns： 12
2) 9
 returns： 10
3) 98
 returns： 101
 99和100都不是“不重复数”， 101是。
4) 21099
 returns： 21201
5) 99123
 returns: 101010
6) 1134567
 returns: 1201010
ok，现在看看解题思路，其实这个题单纯从题本身上看并不复杂，主要是效率问题。估计不会有人一个数一个数地循环查找吧，那样如果给定的long数很大 时，可能会进行成千上万次的循环，会很慢很慢。技巧还是有的，现在来看看怎么快速搞定这个问题。
 首先来拿一个例子看，就选 21099了。
  这个数低两位（99）是重复的。既然要找比21099大的最新不重复数，就需要从这两位开始递增，但不是逐1的递增。比21099大的数是21100，这 个数也是个重复的数，有两对重复的（11和00）。从右侧开始处理它们。先处理00。我们现在要做的就是把00变成不重复的，很简单，就成01就可以了。 现在21100就变成了21101，这个数还是有两个重复数（11）。现在处理11，把11变成12就不重复的，那么现在21101就变成了 21201，ok，现在就得到了最终结果。我们看看，只结果了两步，是很快地，因此，我们可以总结一下算法，步骤如下：
1. 将给定的long数加1。
2.  从这个数开始检测是否为重复数，如果不是，ok，这个数就是最终结果。如果是，那么从数的右侧开始找第1对重复的数，然后将其加1，得到一个新的数。
3. 然后用这个数再从第2步开始。
这个算法首先需要编写一个方法用于将给定数最右侧第一对重复的数找出，并且加1，最后得到一个新的数。如果这个数是不重复的数，那么直接返回0。代码如 下：

<!--<br  />
<br  />
Code highlighting produced by Actipro CodeHighlighter (freeware)<br  />
http://www.CodeHighlighter.com/<br  />
<br  />
-->//sb表示指定的 数，以StringBuilder对象表示
publicstaticlonggetNextNum(StringBuildersb)

{

Stringresult="";
charc='a';//c表示数字中待检测位中高位的字符
inti=0;
for(i=sb.length()-1;i>=0;i--)

{
//如果相邻的两个数字不相同，那么将当前字符保存在c中
if(sb.charAt(i)!=c)

{

c=sb.charAt(i);

}
//如果相邻的两个数字相同，那进行下一步地处理
else

{
//将相同的两个数字组成的数加1
longn=Long.parseLong(String.valueOf(c)+String.valueOf(c))+1;
//先将这两个相同的数字的位置的值设为0，以便进行相加

//计算数字后面要补的0的数，如21443中重复的数字是44，加1后是45，那么首 先将44设成00，
//也就是21003，然后将45后面补0，就是450，最后用21003和450相 加，就变成了21453
intm=sb.length()-i-2;

sb.setCharAt(i,'0');

sb.setCharAt(i+1,'0');
for(intk=0;k<m;k++)

n*=10;
longnum=Long.parseLong(sb.toString())+n;

sb=newStringBuilder(String.valueOf(num));
//  开始将重复数后面的数变成最小的
m=i+2;
for(intx=m;x<sb.length();x++)

{
for(inty=0;y<10;y++)

{

if(sb.charAt(x-1)!=(y+48))

{

sb.setCharAt(x,(char)(y+48));
break;

}

}

}

returnLong.parseLong(sb.toString());

}

}
return0;

}

  要注意的是，虽然把每一对重复的数都变成了不重复的，但仍然不是最小的数，需要将当前重复数后面的数变成最小的，例如，99123将99变成不重复的数， 也就是100，原来的数变成了100123，但100123还需要继续变成100101，再查找重复数，把到了00，再变成101101，然后再变成 101010，就ok了。
 最后调用getNextNum方法来返回最终结果，代码如下：

<!--<br  />
<br  />
Code highlighting produced by Actipro CodeHighlighter (freeware)<br  />
http://www.CodeHighlighter.com/<br  />
<br  />
-->publicstaticlonggetMinNoRepetitionNum(longnum)

{

Strings=String.valueOf(num+1);

longn=0;
longresult=0;
while((n=getNextNum(newStringBuilder(s)))!=0)

{

s=String.valueOf(n);

result=n;

}
if(result==0)
returnnum+1;
else
returnresult;

}

 现在可以使用下面的代码来测试一下：

<!--<br  />
<br  />
Code highlighting produced by Actipro CodeHighlighter (freeware)<br  />
http://www.CodeHighlighter.com/<br  />
<br  />
-->System.out.println(getMinNoRepetitionNum(1999));

乐博Android手机客户端（新浪微博）发布

《银 河系列原创教程》发布

《Java Web开发速学宝典》出版， 欢迎定购

way1
这题数据$10^6$，暴力枚举$i$，然后求$i$的中位因子，复杂度肯定不行，我们考虑到 这样一个性质，$10^6$以内的数的做多因子个数240左右(打表可知)，但大多数都是几十个或者更少，所以对于每个数我们可以把它因子直接给求出来，然后找中位数，对于找他的因子，不能盲目根号n去找，可以先把每个数的最小素因子和最小素因子个数找出来，然后用dfs去找，这样找出来的都是有效的，且时间也不会太多。可以均摊为每个数几十左右，然后对于查找到的直接找到num/2+1那个数，可以用nth_element这个函数求得，
way2
用$fac[i]$表示i离根号i最近的小的那个因子。

因为最近的2个因子一定是在根号n附近，然后埃氏筛又是筛i的倍数

只要枚举的$j$大于等于i的平方，就更新$fac[j] = i$

因为i始终是$j$的因子，只要$i*i<=j$，那么i就更新，

因为$i$一直在变大，后面大的$i$覆盖前面的，直到$i*i>j$之后结束
way1_code
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int man = 1e6+10;
#define IOS ios::sync_with_stdio(0)
#define ull unsigned ll
#define uint unsigned
#define pai pair<int,int>
#define pal pair<ll,ll>
#define IT iterator
#define pb push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define endl '\n'
#define ll long long
const ll mod = 1e9+7;

int prime[man],vis[man];
int m_prime[man],num[man];
void init(){
    int cnt=0;
    for(int i=2;i<man;++i){
        if(!vis[i]){
            prime[++cnt]=i;
			m_prime[i] = i;
			num[i] = 1;
        }
        for(int j=1;j<=cnt&&i*prime[j] < man;++j){
            vis[prime[j]*i]= 1;
            if(i%prime[j]==0){
				m_prime[i*prime[j]] = prime[j];
				num[i*prime[j]] = num[i] + 1;
                break;
            }
			m_prime[i*prime[j]] = prime[j];
			num[i*prime[j]] = 1;
        }
    }
}
ll p[man];
int fac[man],fac_num[man],fac1[man];
int fa_num = 0;
void dfs(int a,int dep,int n){
	if(dep-1==n){
		fac1[++fa_num] = a;
		return;
	}
	for(int i = 0;i <= fac_num[dep];i++){
		if(i!=0)a *= fac[dep];
		dfs(a,dep+1,n);
	}
}

int main() {
	#ifndef ONLINE_JUDGE
		//freopen("in.txt", "r", stdin);
		//freopen("out.txt","w",stdout);
	#endif
	init();
	for(int i = 1;i < man;i++){
		int tp = i;
		int cnt = 0;
		fa_num = 0;
		fac[0] = 1;
		while(tp!=1){
			fac[++cnt] = m_prime[tp];
			fac_num[cnt] = num[tp];
			while(tp%fac[cnt]==0)tp /= fac[cnt];
		}
		dfs(1,0,cnt);
		nth_element(fac1+1,fac1+fa_num/2+1,fac1+1+fa_num);
		p[i] = (p[i-1] + (fac1[fa_num/2+1] + i / fac1[fa_num/2+1])/2)%mod;
	}
	int t;
	cin >> t;
	while(t--){
		int n;cin >> n;
		cout <<p[n] << endl;
	}
	return 0;
}

way2_code
#pragma GCC optimize(2)
#include<bits/stdc++.h>
using namespace std;
const int man = 1e6+10;
#define IOS ios::sync_with_stdio(0)
#define ull unsigned ll
#define uint unsigned
#define pai pair<int,int>
#define pal pair<ll,ll>
#define IT iterator
#define pb push_back
#define fi first
#define se second
#define For(i,j,k) for (int i=(int)(j);i<=(int)(k);i++)
#define Rep(i,j,k) for (int i=(int)(j);i>=(int)(k);i--)
#define endl '\n'
#define ll long long
const ll mod = 1e9+7;
int fac[man];
 
void init(){
    for(int i = 1;i < man;i++){
        for(int j = i;j < man;j += i){
            if(1ll * i * i <= j)fac[j] = i;
        }
    }
}
 
int main() {
    #ifndef ONLINE_JUDGE
        //freopen("in.txt", "r", stdin);
        //freopen("out.txt","w",stdout);
    #endif
    init();
    int t;
    cin >> t;
    while(t--){
        int n;
        cin >> n;
        ll ans = 0;
        for(int i = 1;i <= n;i++){
            ans = (ans + (fac[i] + i / fac[i])/2 ) %mod;
        }
        cout <<ans << endl;
    }
    return 0;
}

题意 史密斯数定义：一个数按十进制位拆分求和 == 这个数分解质因数后，所有质因数十进制位拆分求和的和，但该数不能使质数。然后给你一个数n，问你比它大的最小史密斯数是几。
思路 纯暴力即可，但要注意排除质数，并且是大于n不是大于等于n。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#include <cstring>
#include <string>
#include <cstdlib>
#include <map>
using namespace std;
#define I64_MAX 9223372036854775807 
typedef long long ll;
const double pi=acos (-1.0);
const double eps=1e-8 ;
//const ll INF=(I64_MAX)/2;
//#pragma comment(linker, "/STACK:102400000,102400000")
const int inf=0x3f3f3f3f ;
#define maxx(a) memset(a, 0x3f, sizeof(a))
#define zero(a) memset(a, 0, sizeof(a))
#define FILL(a,b) memset(a, b, sizeof(a))
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define srep(i,n) for(i = 1;i <= n;i ++)
#define snuke(c,itr) for( __typeof((c).begin()) itr=(c).begin();itr!=(c).end();itr++)
#define MP make_pair
#define fi first
#define se second
typedef pair <int, int> PII;
typedef pair <ll, ll> PX;
typedef pair<int,ll> PIL;
#define MAX

ll n;
vector<ll> vec;

int getSum(ll x)
{
	int res = 0;
	while(x > 0)
	{
		res += (int)(x % (ll)10);
		x /= 10;
	}
	return res;
}

int fenJie(ll x,vector<ll>& v)
{
	ll i = 2;
	v.clear();
	while(i*i <= x)
	{
		while(x%i == 0)
		{
			x /= i;
			v.push_back(i);
		}
		i++;
	}
	if(x > 1) //x is a zhiShu
	{
		v.push_back(x);
	}
	return v.size();
}

int main ()
{
    // freopen("E:\\input.txt" ,"r", stdin);
     // freopen ("E:\\out.txt","w",stdout);
	ll i;
	int j;
	while(scanf("%lld",&n) != EOF)
	{
		if(n==0)
			break;
		for(i=n+1;1;i++)
		{
			int sum1 = 0,sum2 = 0;
			sum1 = getSum(i);
			fenJie(i,vec);
			if(vec.size() == 1)
				continue;
			for(j=0;j<vec.size();j++)
			{
				sum2 += getSum(vec[j]);
			}
			if(sum1 == sum2)
			{
				printf("%lld\n",i);
				break;
			}
		}
		
		
	}

	return 0;
}