babak's blog

sgu 537
By babak, 13 years ago, In English

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;
}
Tags sgu
  • Vote: I like it
  • -15
  • Vote: I do not like it

13 years ago, # |
  Vote: I like it +1 Vote: I do not like it
abcdefghijaaa
Right answer: 1 3

By the way,
→ Reply
»
12 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Time limit exceeded 103. Please, help. Code.

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    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.

    → Reply