Re: Can "cout" do evil?
thomas wrote:
#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[i]==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
tazmaster@rocketmail.com