- 注册时间
- 2007-12-27
- 最后登录
- 1970-1-1
- 威望
- 星
- 金币
- 枚
- 贡献
- 分
- 经验
- 点
- 鲜花
- 朵
- 魅力
- 点
- 上传
- 次
- 下载
- 次
- 积分
- 40149
- 在线时间
- 小时
|
发表于 2010-6-22 11:21:44
|
显示全部楼层
代码:-
- // mc.cpp : Defines the entry point for the console application.
- //
-
- #include "stdafx.h"
- #include <algorithm>
- #include <set>
- #include <vector>
- using namespace std;
- #define MAXV 87655
- short dmask[MAXV];
- set<short> sets[MAXV];
- typedef struct{
- int x[8];
- int& operator[](int k){return x[k];}
- }LE;
-
- void dumpLE(LE x)
- {
- int i;
- printf("%d",x[0]);
- for(i=1;i<8;i++){
- if(x[i]>=0){
- printf("*%d",x[i]);
- }else{
- break;
- }
- }
- }
-
- LE temp;
-
- void searchd(int target, int factorbound, short mask, int uindex, vector<LE>& vr)
- {
- if(target<factorbound&&dmask[target]==mask){
- temp[uindex]=target;
- if(uindex+1<8){
- temp[uindex+1]=-1;
- }
- vr.push_back(temp);
- }else if(target<factorbound&&(dmask[target]|(1<<1))==mask){
- temp[uindex]=target;
- temp[uindex+1]=1;
- if(uindex+2<8){
- temp[uindex+2]=-1;
- }
- vr.push_back(temp);
- }
- int i;
- i=(target+factorbound-1)/factorbound;
- if(i<2)i=2;
- for(;i*i<target;i++){
- if(target%i==0){
- int k=target/i;
- if(k<factorbound&&(dmask[k]&mask)==dmask[k]){///use it
- if(sets[i].find(mask&(~dmask[k]))!=sets[i].end()){
- temp[uindex]=k;
- searchd(i,k,mask&(~dmask[k]),uindex+1,vr);
- }
- }
- }
- }
- --i;
- if(i>=factorbound)i=factorbound-1;
- for(;i>=2;i--){
- if(target%i==0){
- if((dmask[i]&mask)==dmask[i]){
- if(sets[target/i].find(mask&(~dmask[i]))!=sets[target/i].end()){
- temp[uindex]=i;
- searchd(target/i,i,mask&(~dmask[i]),uindex+1,vr);
- }
- }
- }
- }
- }
-
- void getvlist(int target, short mask, vector<LE>& vr)
- {
- searchd(target, target+1, mask, 0, vr);
- }
-
- void output(int target, short mask1, short mask2)
- {
- vector<LE> list1;
- vector<LE> list2;
- getvlist(target,mask1, list1);
- getvlist(target,mask2, list2);
- unsigned i,j;
- for(i=0;i<list1.size();i++){
- for(j=0;j<list2.size();j++){
- dumpLE(list1[i]);
- printf("=");
- dumpLE(list2[j]);
- printf("\n");
- }
- }
- }
-
- void process_sets()
- {
- int i;
- for(i=2;i<MAXV;i++){
- set<short>::iterator it1,it2;
- for(it1=sets[i].begin();it1!=sets[i].end();++it1){
- if(((*it1)&512)!=0)///skip duplicated case
- continue;
- it2=sets[i].find(1023^(*it1));
- if(it2!=sets[i].end()){
- output(i,*it1,*it2);
- }
- }
- }
- }
-
- void initsets()
- {
- int i,j;
- for(i=2;i<MAXV;i++){
- if(dmask[i]>=0){
- sets[i].insert(dmask[i]);///the integer itself
- if((dmask[i]&(1<<1))==0){///if integer 1 not used
- sets[i].insert(dmask[i]|(1<<1));///1*i
- }
- }
- for(j=2;j*j<i;j++){
- if(i%j==0){
- int k=i/j;
- set<short>::iterator it1, it2;
- for(it1=sets[j].begin();it1!=sets[j].end();++it1){
- for(it2=sets[k].begin();it2!=sets[k].end();++it2){
- if(((*it1)&(*it2))==0){
- sets[i].insert((*it1)|(*it2));///by formula i=j*k
- }
- }
- }
- }
- }
- }
- }
-
- void initmask()
- {
- int i;
- dmask[0]=-1;
- for(i=1;i<MAXV;i++){
- int t=0,u=i;
- while(u>0){
- int d=u%10;
- if(t&(1<<d)){
- t=-1;
- break;
- }
- t|=1<<d;
- u/=10;
- }
- dmask[i]=t;
- }
- }
-
-
- int _tmain(int argc, _TCHAR* argv[])
- {
- initmask();
- initsets();
- process_sets();
- return 0;
- }
复制代码 代码思路是首先数据分成两边,必然有一边使用了不超过5个数据。而且如果两边都是用5个数,那么有一边的最大数字是8,所以等号两边的数值最大只能87654.
于是等号两边都可以写成一个不超过87654的数的因子分解形式。
于是我们想办法对两边都进行因子分解,而且各因子用掉的数字都要不同,两边正好用掉10个数字。 |
评分
-
查看全部评分
|