Can "cout" do evil?

[thomas]

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<iterator>
#include<string>
#include<algorithm>

using namespace std;

#define M 1000009

vector<int> primes;

//generate C(n, 1), C(n, 2), ...
void dfs(vector<int> &mp, int its, int i, vector<int> &temp){
if(i==0) {
int s=1;
for(vector<int>::iterator it2(temp.begin()); it2!=temp.end();
it2++){ s=s*(*it2); }
if(s>1) mp.push_back(s); return;
}
if(mp[its]==0) return;
int my_its(its);
for(vector<int>::iterator it_t(mp.begin() + its); *it_t!=0; it_t+
+, my_its++){
temp.push_back(*it_t);
dfs(mp, my_its+1, i-1, temp);
temp.pop_back();
}
}

int main(){
vector<int> numbers; numbers.resize(M, 0);

//generate prime numbers
primes.push_back(2);
for(int i=3; i<M; i+=2){
if(numbers==1) continue;
primes.push_back(i);
for(int j=i+i; j<M; j+=i)
numbers[j] = 1;
}

int m, k;
while(cin>>m>>k){
vector<int> mprime; int mm=m;
cout<<1; //<1>

//prime factors of m
for(vector<int>::iterator it(primes.begin()); it!=primes.end()
&&*it<=mm; it++){
if(mm%(*it)==0) mprime.push_back(*it);
while(mm%(*it)==0) mm=mm/(*it);
}

//generate C(n,i), push the multiplication result of the "i" factors
in mprime, seperated by 0
int msize = mprime.size();
mprime.push_back(0);
for(int i=2; i<=msize; i++){
vector<int> temp;
dfs(mprime, 0, i, temp);
mprime.push_back(0);
}

//calculate the k-th number x with gcd(x,m)=1
int result = 0; int total=0; bool change=true;
while(total<k){
result += (k-total); total=result;
for(vector<int>::iterator it(mprime.begin()); it!
=mprime.end()&&*it<=m&&*it<=result; it++){
if(*it==0){ change=(change?false:true); continue;}
if(change) total-=(result/(*it));
else total+=(result/(*it));
}
}
cout<<result<<endl;
}
}

---------code--------
The above is the code to calculate the k-th number x of m having
gcd(x,m)=1
notice the line marked <1>
If the <1> line exists, everything works fine.
But if I remove line <1>, the guy says error.
what's wrong? Can a simple "cout" do anything evil?

 

[saya-jin]

Sorry dude, but this program with or without the line <1> works. There
is another issue with this code but this issue isn't related with the
cout stream. On Visual C++ 2005 compiler...

saya-jin

 

[Jim Langston]

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<iterator>
#include<string>
#include<algorithm>

using namespace std;

#define M 1000009

vector<int> primes;

//generate C(n, 1), C(n, 2), ...
void dfs(vector<int> &mp, int its, int i, vector<int> &temp){
if(i==0) {
int s=1;
for(vector<int>::iterator it2(temp.begin()); it2!=temp.end();
it2++){ s=s*(*it2); }
if(s>1) mp.push_back(s); return;
}
if(mp[its]==0) return;
int my_its(its);
for(vector<int>::iterator it_t(mp.begin() + its); *it_t!=0; it_t+
+, my_its++){
temp.push_back(*it_t);
dfs(mp, my_its+1, i-1, temp);
temp.pop_back();
}
}

int main(){
vector<int> numbers; numbers.resize(M, 0);

//generate prime numbers
primes.push_back(2);
for(int i=3; i<M; i+=2){
if(numbers==1) continue;
primes.push_back(i);
for(int j=i+i; j<M; j+=i)
numbers[j] = 1;
}

int m, k;
while(cin>>m>>k){
vector<int> mprime; int mm=m;
cout<<1; //<1>

//prime factors of m
for(vector<int>::iterator it(primes.begin()); it!=primes.end()
&&*it<=mm; it++){
if(mm%(*it)==0) mprime.push_back(*it);
while(mm%(*it)==0) mm=mm/(*it);
}

//generate C(n,i), push the multiplication result of the "i" factors
in mprime, seperated by 0
int msize = mprime.size();
mprime.push_back(0);
for(int i=2; i<=msize; i++){
vector<int> temp;
dfs(mprime, 0, i, temp);
mprime.push_back(0);
}

//calculate the k-th number x with gcd(x,m)=1
int result = 0; int total=0; bool change=true;
while(total<k){
result += (k-total); total=result;
for(vector<int>::iterator it(mprime.begin()); it!
=mprime.end()&&*it<=m&&*it<=result; it++){
if(*it==0){ change=(change?false:true); continue;}
if(change) total-=(result/(*it));
else total+=(result/(*it));
}
}
cout<<result<<endl;
}
}

---------code--------
The above is the code to calculate the k-th number x of m having
gcd(x,m)=1
notice the line marked <1>
If the <1> line exists, everything works fine.
But if I remove line <1>, the guy says error.
what's wrong? Can a simple "cout" do anything evil?

Generally this type of problem, removing something that should have no
affect on the program will cause a program fault with or with out it,
generally this means you have undefined behavior in your program.

Undefined behavior can change as your program changes.

Usually the undefined behavior is a buffer overflow or underflow,
overwritting a buffer somewhere. Sometimes this will make a program crash,
sometimes it won't, it all depends on what happens to be in the memory the
buffer is overwriting. And when you change a program the layout tends to
change chaning what is being overwritten.

To test this since you are using vectors, isntead of:
numbers[j] ...
change it to
numbers.at(j) ...
at() checks and makes sure the index is inside the bounds of the array. If
it is not at() will throw an error you can detect.

Give it a try.

 

[thomas]

#include<iostream>
#include<vector>
#include<map>
#include<set>
#include<iterator>
#include<string>
#include<algorithm>

using namespace std;

#define M 1000009

vector<int> primes;

//generate C(n, 1), C(n, 2), ...
void dfs(vector<int> &mp, int its, int i, vector<int> &temp){
   if(i==0) {
       int s=1;
       for(vector<int>::iterator it2(temp.begin()); it2!=temp.end();
it2++){        s=s*(*it2);        }
       if(s>1) mp.push_back(s);   return;
   }
   if(mp[its]==0) return;
   int my_its(its);
   for(vector<int>::iterator it_t(mp.begin() + its); *it_t!=0;  it_t+
+, my_its++){
       temp.push_back(*it_t);
       dfs(mp, my_its+1, i-1, temp);
       temp.pop_back();
   }
}

int main(){
   vector<int> numbers;    numbers.resize(M, 0);

//generate prime numbers
   primes.push_back(2);
   for(int i=3; i<M; i+=2){
       if(numbers==1) continue;
       primes.push_back(i);
       for(int j=i+i; j<M; j+=i)
           numbers[j] = 1;
   }

   int m, k;
   while(cin>>m>>k){
       vector<int> mprime;   int mm=m;
       cout<<1;              //<1>

//prime factors of m
       for(vector<int>::iterator it(primes.begin()); it!=primes.end()
&&*it<=mm; it++){
           if(mm%(*it)==0) mprime.push_back(*it);
           while(mm%(*it)==0) mm=mm/(*it);
       }

//generate C(n,i), push the multiplication result of the "i" factors
in mprime, seperated by 0
       int msize = mprime.size();
       mprime.push_back(0);
       for(int i=2; i<=msize; i++){
           vector<int> temp;
           dfs(mprime, 0, i, temp);
           mprime.push_back(0);
       }

//calculate the k-th number x with gcd(x,m)=1
       int result = 0;   int total=0;  bool change=true;
       while(total<k){
           result += (k-total);    total=result;
           for(vector<int>::iterator it(mprime.begin()); it!
=mprime.end()&&*it<=m&&*it<=result; it++){
               if(*it==0){ change=(change?false:true); continue;}
               if(change)    total-=(result/(*it));
               else total+=(result/(*it));
           }
       }
       cout<<result<<endl;
   }
}

---------code--------
The above is the code to calculate the k-th number x of m having
gcd(x,m)=1
notice the line marked <1>
If the <1> line exists, everything works fine.
But if I remove line <1>, the guy says error.
what's wrong? Can a simple "cout" do anything evil?

Generally this type of problem, removing something that should have no
affect on the program will cause a program fault with or with out it,
generally this means you have undefined behavior in your program.

Undefined behavior can change as your program changes.

Usually the undefined behavior is a buffer overflow or underflow,
overwritting a buffer somewhere.  Sometimes this will make a program crash,
sometimes it won't, it all depends on what happens to be in the memory the
buffer is overwriting.  And when you change a program the layout tends to
change chaning what is being overwritten.

To test this since you are using vectors, isntead of:
numbers[j] ...
change it to
numbers.at(j) ...
at() checks and makes sure the index is inside the bounds of the array.  If
it is not at() will throw an error you can detect.

Give it a try.

--
Jim Langston
(e-mail address removed)- Hide quoted text -

- Show quoted text -

yeah, I got the problem. It indeed has nothing to do with "cout".
It's about the iterator invalidation issue.
anyway, thanks for your help. love you guys.