#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
#include<map>
#include<queue>
#include<math.h>
using namespace std;
typedef map<long long,vector<string> > LIST;
string _s="";
void constructeString(vector<long long> &a,LIST&list,long long n,long long depth=0){
if(depth==a.size()){
_s[_s.length()-1]='=';
cout << _s <<n<<endl;
return ;
}
for (auto&& str : list[a[depth]]) {
string s=_s;
_s+=str+"+";
constructeString(a,list,n,depth+1);
_s=s;
}
}
bool dfs(vector<long long> &v,LIST &list,int n,int value,int depth=0){
if(depth==(v.size()-1)){
if(list.count(value)){
v[depth]=value;
for(int i=0;i<v.size()-1;i++)if(v[i]>v[i+1])return false;
constructeString(v,list,n);
return true;
}
return false;
}
bool f=false;
for(auto&it:list){
if(value>=it.first ){
v[depth]=it.first;
bool g = dfs(v,list,n,value-it.first,depth+1);
f=f||g;
v[depth]=0;
}
}
return f;
}
void createList(long long n,LIST &list){
for (long long i = 2; i <= sqrt(n); i++) {
long long p=2;
for (long long l = i*i; l <= n; l*=i) {
list[l].push_back(to_string(i)+"^"+to_string(p));
p++;
}
}
}
bool hoge(long long n,long long m){
cout <<endl;
LIST list;
vector<long long> v(m);
createList(n,list);
bool f = dfs(v,list,n,n);
if(!f)cout << "Σ_{i=0}^{i<"<<m<<"}a_i^{b_i} ="<<n<<": no "<<endl;
return f;
}
int main(){
long long n[]={2017,2017,20017,200017,2000017,20000017,200000017,2000000017,20000000017,200000000017,2000000000017,997};
long long m[]={2,3,2,2,2,2,2,2,2,2,2,4};
for (long long i = 0; i < sizeof(n)/sizeof(long long); i++) {
hoge(n[i],m[i]);
}
}
I2luY2x1ZGU8aW9zdHJlYW0+CiNpbmNsdWRlPHZlY3Rvcj4KI2luY2x1ZGU8c3RyaW5nPgojaW5jbHVkZTx1bm9yZGVyZWRfbWFwPgojaW5jbHVkZTxtYXA+CiNpbmNsdWRlPHF1ZXVlPgojaW5jbHVkZTxtYXRoLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIG1hcDxsb25nIGxvbmcsdmVjdG9yPHN0cmluZz4gPiBMSVNUOwoKc3RyaW5nIF9zPSIiOwp2b2lkIGNvbnN0cnVjdGVTdHJpbmcodmVjdG9yPGxvbmcgbG9uZz4gJmEsTElTVCZsaXN0LGxvbmcgbG9uZyBuLGxvbmcgbG9uZyBkZXB0aD0wKXsKICBpZihkZXB0aD09YS5zaXplKCkpewogICAgX3NbX3MubGVuZ3RoKCktMV09Jz0nOwogICAgY291dCA8PCBfcyA8PG48PGVuZGw7CiAgICByZXR1cm4gOwogIH0KICBmb3IgKGF1dG8mJiBzdHIgOiBsaXN0W2FbZGVwdGhdXSkgewogICAgc3RyaW5nIHM9X3M7CiAgICBfcys9c3RyKyIrIjsKICAgIGNvbnN0cnVjdGVTdHJpbmcoYSxsaXN0LG4sZGVwdGgrMSk7CiAgICBfcz1zOwogIH0KfQoKYm9vbCBkZnModmVjdG9yPGxvbmcgbG9uZz4gJnYsTElTVCAmbGlzdCxpbnQgbixpbnQgdmFsdWUsaW50IGRlcHRoPTApewoJaWYoZGVwdGg9PSh2LnNpemUoKS0xKSl7CgkJaWYobGlzdC5jb3VudCh2YWx1ZSkpewoJCQl2W2RlcHRoXT12YWx1ZTsKCQkJZm9yKGludCBpPTA7aTx2LnNpemUoKS0xO2krKylpZih2W2ldPnZbaSsxXSlyZXR1cm4gZmFsc2U7CgkJCWNvbnN0cnVjdGVTdHJpbmcodixsaXN0LG4pOwoJCQlyZXR1cm4gdHJ1ZTsKCQl9CgkJcmV0dXJuIGZhbHNlOwoJfQoJYm9vbCBmPWZhbHNlOwoJZm9yKGF1dG8maXQ6bGlzdCl7CgkJaWYodmFsdWU+PWl0LmZpcnN0ICl7CgkJCQoJCQl2W2RlcHRoXT1pdC5maXJzdDsKCQkJYm9vbCBnID0gZGZzKHYsbGlzdCxuLHZhbHVlLWl0LmZpcnN0LGRlcHRoKzEpOwoJCQlmPWZ8fGc7CgkJCXZbZGVwdGhdPTA7CgkJfQkKCX0KCXJldHVybiBmOwp9Cgp2b2lkIGNyZWF0ZUxpc3QobG9uZyBsb25nIG4sTElTVCAmbGlzdCl7CiAgZm9yIChsb25nIGxvbmcgaSA9IDI7IGkgPD0gc3FydChuKTsgaSsrKSB7CiAgICBsb25nIGxvbmcgcD0yOwogICAgZm9yIChsb25nIGxvbmcgIGwgPSBpKmk7IGwgPD0gbjsgbCo9aSkgewogICAgICBsaXN0W2xdLnB1c2hfYmFjayh0b19zdHJpbmcoaSkrIl4iK3RvX3N0cmluZyhwKSk7CiAgICAgIHArKzsKICAgIH0KICB9Cn0KCmJvb2wgaG9nZShsb25nIGxvbmcgbixsb25nIGxvbmcgbSl7CiAgY291dCA8PGVuZGw7CiAgTElTVCBsaXN0OwogIHZlY3Rvcjxsb25nIGxvbmc+IHYobSk7CiAgY3JlYXRlTGlzdChuLGxpc3QpOwogIGJvb2wgZiA9IGRmcyh2LGxpc3QsbixuKTsKICBpZighZiljb3V0IDw8ICLOo197aT0wfV57aTwiPDxtPDwifWFfaV57Yl9pfSA9Ijw8bjw8Ijogbm8gIjw8ZW5kbDsKICByZXR1cm4gZjsKfQoKCmludCBtYWluKCl7CiAgbG9uZyBsb25nIG5bXT17MjAxNywyMDE3LDIwMDE3LDIwMDAxNywyMDAwMDE3LDIwMDAwMDE3LDIwMDAwMDAxNywyMDAwMDAwMDE3LDIwMDAwMDAwMDE3LDIwMDAwMDAwMDAxNywyMDAwMDAwMDAwMDE3LDk5N307CiAgbG9uZyBsb25nIG1bXT17MiwzLDIsMiwyLDIsMiwyLDIsMiwyLDR9OwogIGZvciAobG9uZyBsb25nIGkgPSAwOyBpIDwgc2l6ZW9mKG4pL3NpemVvZihsb25nIGxvbmcpOyBpKyspIHsKICAgIGhvZ2UobltpXSxtW2ldKTsKICB9Cn0K