I give wrong answer on test 48 and I don't what is the problem with my code.
#include <iostream>
#include <map>
#include <set>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
#define REP(i,n) for((i)=0;(i)<(n);(i)++)
ll gcd(ll a, ll b){
if(b==0)
return a;
return gcd(b,a%b);
}
void solve(vector<ll> &v , ll n){
ll i;
for(i=1;i*i<=n;i++){
if(n%i==0){
v.push_back(i);
if(i*i!=n)
v.push_back(n/i);
}
}
sort(v.begin(),v.end());
}
int main(){
int tsc,tcc,i,n;
ll t,ans;
string s;
cin>>tsc;
REP(tcc,tsc){
map<char,ll> mp;
map<char,ll>::iterator it;
cin>>s;
ans = 0;
n = s.size();
t=1;
for(i=n-1;i>=0;i--){
mp[s[i]]+=t;
t*=10;
}
for(it=mp.begin();it!=mp.end();it++)
ans = gcd(ans,it->second);
cout<<"Case "<<tcc+1<<":";
if(mp.size()==10){
if(n==10){
cout<<" 1 3 9"<<endl;
continue;
}
if(n==13 && s[0]==s[1] && s[0]==s[2] && s[0]==s[3]){
cout<<" 1 3"<<endl;
continue;
}
cout<<" 1"<<endl;
continue;
}
vector<ll> v;
solve(v,ans);
REP(i,v.size())
cout<<" "<<v[i];
cout<<endl;
}
return 0;
}
Right answer: 1 3
By the way,
Time limit exceeded 103. Please, help. Code.
you can find all prime divisors and it's powers. than generate all possible composite divisors. there is about 700 000 prime numbers up to 10^7, and it will take only 700 k divisions, instead of current 10^7.
Thank you very much, I will try it.