本文主要是介绍CF 61 div2 D. Petya and His Friends,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
题目:D - Petya and His Friends
思路:高精度模板可以过,但是找规律也行
高精度的:
#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <sstream>
#include <map>
using namespace std;
#define maxn 240
bool vis[maxn];
map<string,int>m;
stringstream ss;
string sss;
void Prime()
{m.clear();memset(vis,true,sizeof(vis));vis[0]=vis[1]=false;for(int i=2;i<maxn;i++){if(vis[i]){ss.clear();ss<<i;ss>>sss;m[sss]++;for(int j=2*i;j<maxn;j+=i)vis[j]=0;}}
}
struct BigInt
{string a;int sign;BigInt() {} // default constructorBigInt(string b){ // constructor for string(*this)=b;}int size(){return a.size();}BigInt inverseSign(){sign*=-1;return (*this);}BigInt normalize(int newSign){ // remove leading zero and fix signfor(int i=a.size()-1;i>0&&a[i]=='0';i--)a.erase(a.begin()+i);sign=(a.size()==1 &&a[0]=='0' )?1:newSign;return (*this);}void operator = (string b){a=b[0]=='-'?b.substr(1):b;reverse(a.begin(),a.end());this->normalize(b[0]=='-'?-1:1);}bool operator < (const BigInt &b) const{if(sign!=b.sign) return sign<b.sign;if(a.size()!=b.a.size())return sign==1?a.size()<b.a.size():a.size()>b.a.size();for(int i=a.size()-1;i>=0;i--)if(a[i]!=b.a[i])return sign==1?a[i]<b.a[i]:a[i]>b.a[i];return false;}bool operator == (const BigInt &b) const{return a==b.a && sign==b.sign ;}BigInt operator + (BigInt b){if(sign!=b.sign)return (*this)- b.inverseSign();BigInt c;for(int i=0,carry=0;i<a.size()||i<b.size()||carry;i++){carry+=(i<a.size()?a[i]-48:0)+(i<b.size()?b.a[i]-48:0);c.a+=(carry%10+48);carry/=10;}return c.normalize(sign);}BigInt operator - (BigInt b){if(sign!=b.sign)return (*this) + b.inverseSign();int s=sign;sign=b.sign=1;if((*this)<b)return ((b-(*this)).inverseSign()).normalize(-s);BigInt c;for(int i=0,borrow=0;i<a.size();i++){borrow=a[i]-borrow-(i<b.size()?b.a[i]:48);c.a+=borrow>=0?borrow+48:borrow+58;borrow=borrow>=0?0:1;}return c.normalize(s);}BigInt operator * (BigInt b){BigInt c("0");for(int i=0,k=a[i]-48;i<a.size();i++,k=a[i]-48){while(k--) c=c+b;b.a.insert(b.a.begin(),'0');}return c.normalize(sign*b.sign);}BigInt operator / (BigInt b){if(b.size()==1 && b.a[0]=='0')b.a[0]/=(b.a[0]-48);BigInt c("0"),d;for(int j=0;j<a.size();j++)d.a+="0";int dsign=sign*b.sign;b.sign=1;for(int i=a.size()-1;i>=0;i--){c.a.insert(c.a.begin(),'0');c=c+a.substr(i,1);while(!(c<b))c=c-b,d.a[i]++;}return d.normalize(dsign);}BigInt operator % (BigInt b){if(b.size()==1 && b.a[0]=='0')b.a[0]/=(b.a[0]-48);BigInt c("0");b.sign=1;for(int i=a.size()-1;i>=0;i--){c.a.insert(c.a.begin(),'0');c=c+a.substr(i,1);while(!(c<b))c=c-b;}return c.normalize(sign);}void Print(){if(sign==-1) putchar('-');for(int i=a.size()-1;i>=0;i--)putchar(a[i]);cout<<endl;}
};
int main()
{Prime();int n;cin>>n;if(n==1||n==2){cout<<-1<<endl;return 0;}sss="1";BigInt cnt,ans=sss;map<string,int>::iterator it=m.begin();for(int i=1;i<=n;i++){cnt=it->first;ans=ans*cnt;it++;}it=m.begin();for(int i=1;i<=n;i++){cnt=it->first;cnt=ans/cnt;it++;cnt.Print();}return 0;
}
找规律的话,假设a,b,c是素数,第一个数是a*b,第二个数是b*c,后面的数是 a*c*i (1<=i<=n-2)
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <iostream>
#define MAXN 100000
using namespace std;
int main()
{int n;cin>>n;if(n<=2)cout<<-1<<endl;else{cout<<35<<endl;cout<<77<<endl;for(int i=1;i<=n-2;i++)cout<<55*i<<endl;}return 0;
}
这篇关于CF 61 div2 D. Petya and His Friends的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!