Re: Can "cout" do evil?
On May 2, 7:42 pm, "Jim Langston" <tazmas...@rocketmail.com> wrote:
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!=prime=
s.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=tru=
e;
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:tr=
ue); 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 cra=
sh,
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 t=
o
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
tazmas...@rocketmail.com- 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.