mobius.cpp

Mobius 反演定理的 实现 用 STL 编写

/************************************************************************/
/*                           Mobius                                     */
/************************************************************************/
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class mobius
{
public:
	mobius():x(x),sushu(0),yinzi(0){}
	~mobius(){delete sushu; delete yinzi;}
	void sub();
	bool dif(const vector<int>*);
private:
	int x;
	vector<int> * sushu;
	vector<int> * yinzi;
};

void main()
{
	mobius q;
	q.sub();
}

bool mobius::dif(const vector<int>*)
{
	bool ys_no;
	vector<int>::iterator it;
	it=yinzi->begin();
	while (it!=yinzi->end())
	{
		if (it==yinzi->end()-1)
		{
			break;
		}
		if (*it==*(it+1))                   
		{
			ys_no=false;
			break;
		}
		else
		{
			ys_no=true;
		}
		it++;
	}
        return ys_no; 
}

void mobius::sub()
{
	sushu=new vector<int>;
	yinzi=new vector<int>;
	vector<int>::iterator iter,result;
	cout<<"Enter a num:"<<endl;
	cin>>x;
	for (int i=2;i<=x;i++)
	{
		sushu->push_back(i);
	}
	//copy(sushu->begin(),sushu->end(),ostream_iterator<int>(cout," "));
	iter=sushu->begin();
	while (iter!=sushu->end())
	{
		for (int j=2;j<*iter;j++)
		{
			if (*iter%j==0)
			{
				*iter=-1;
				break;
			}
		}
		iter++;
	}
	result=remove(sushu->begin(),sushu->end(),-1);
	sushu->erase(result,sushu->end());

	int b=x;
	
	iter=sushu->begin();
	while (iter!=sushu->end())
	{
		while (b%*iter==0)
		{
			yinzi->push_back(*iter);
			b=b/(*iter);
		}
		iter++;
	}
	if (x==1)
	{
		yinzi->push_back(1);
	}	
	cout<<x<<"的因子:"<<endl;
	copy(yinzi->begin(),yinzi->end(),ostream_iterator<int>(cout," "));
	cout<<endl;
	if (x==1)
	{
		cout<<x<<"的函数值："<<1<<endl;
	}	
	if (yinzi->size()==1&&x!=1)
	{
		cout<<x<<"的函数值："<<-1<<endl;
	}
	else
	{
         if (dif(yinzi)==true)                          //组成因子完全不同
		 {
	 	     if (yinzi->size()%2==0)
			 {
			    cout<<x<<"的函数值："<<1<<endl;
			 }
		     if (yinzi->size()%2!=0)
			 {			
			    cout<<x<<"的函数值："<<-1<<endl;
			 }
		 }
		 if (dif(yinzi)==false)                          //组成因子相同 
		 {
		      cout<<x<<"的函数值："<<0<<endl;
		 }
	
	}	
	//cout<<dif(yinzi);
}