国赛集训-AOJ-分解篇

本文主要是介绍国赛集训-AOJ-分解篇，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

三个师妹之出题
Description
这一次,那几个师妹给sharp出了一个题目:给定一个正整数N,求1/X+1/Y= 1/N的所有正整数解.sharp哈哈笑了两声,很简单的题目嘛…但是他一听数据范围就傻眼了,N最大可能是999999999!!!聪明的你能帮帮可怜的sharp吗?好让他不那么丢脸.

Input
第一行输入一个正整数M,下面有M行,每一行都是一个正整数N.

Output
输出共M行,每行都是方程解的个数.

Sample Input
2
1
2
Sample Output
1
3

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<vector>
#include<algorithm>
#include<cmath>
using namespace std;
long long a[20],b[20];
long long gs;
int main()
{long long n,i,j,k,x,z,ans;scanf("%lld",&x);for(k=1;k<=x;k++){scanf("%lld",&n);z=n;memset(b,0,sizeof(b));memset(a,0,sizeof(a));if(n<=3){gs=1;a[0]=n;b[0]=1;}else{gs=0;i=2;while(i*i<=n){while(n%i==0){b[gs]++;n/=i;}if(b[gs]>0){a[gs]=i;gs++;}i++;}if(n>1){a[gs]=n;b[gs]=1;gs++;}}if(z<2){cout<<1<<endl;}else{ans=1;for(i=0;i<gs;i++){ans*=2*b[i]+1;}cout<<ans<<endl;}}return 0;
}

整数分解
Description
根据数论的有关理论可知，任何大于1的正整数都可唯一地表示为形如(P1^N1)*(P2N2)*…(Pm^Nm)的形式。请你编程序实现。

Input
输入：第一行是测试数据的组数N(N小于10000)，接着是N行正整数，每行一个，每个正整数不超过32767。

Output
输出：形式是M=(P1^N1)*(P2N2)*…(Pm^Nm)。

说明：（a）如果幂的值为1，则不用写括号和1次幂；如：15=3*5。

（b）如果N是素数，也不用写括号和1次幂；如：7=7。

（c）如果因子只有一个，也不用写括号；如：27=3^3。

Sample Input
2
25608
24027
Sample Output
25608=(2^3)31197
24027=38009

#include<bits/stdc++.h>
using namespace std;
struct jg
{int p,m;
};
jg a[21];
bool ss(int x);
int main()
{int n,i,k,x,t,c;cin>>n;for(k=1;k<=n;k++){for(i=1;i<=20;i++){a[i].m=0;a[i].p=0;}t=0;scanf("%d",&x);cout<<x<<'=';if(x==1){cout<<1<<'^'<<0<<endl;continue;}c=x;for(i=2;i<=x;i++){if(x%i==0){t++;}while(x%i==0&&x!=0){a[t].p=i;a[t].m++;x/=i;}}if(ss(c)){cout<<c<<endl;}else{if(a[2].m==0&&a[2].p==0){cout<<a[1].p<<'^'<<a[1].m<<endl;}else{for(i=1;i<t;i++){if(a[i].m==1){cout<<a[i].p<<'*';}else{cout<<'('<<a[i].p<<'^'<<a[i].m<<")*";}}if(a[t].m==1){cout<<a[t].p<<endl;}else{cout<<'('<<a[t].p<<'^'<<a[t].m<<')'<<endl;}}}}return 0;
}
bool ss(int x)
{int i;if(x==2){return true;}if(x<3){return false;}for(i=2;i<=sqrt(x);i++){if(x%i==0){return false;}}return true;
}

找新朋友
Description
新年快到了，“猪头帮协会”准备搞一个聚会，已经知道现有会员N人，把会员从1到N编号，其中会长的号码是N号，凡是和会长是老朋友的，那么该会员的号码肯定和N有大于1的公约数，否则都是新朋友，现在会长想知道究竟有几个新朋友？请你编程序帮会长计算出来。

Input
输入：第一行是测试数据的组数CN（Case number，1<cn<10000），接着有CN行正整数N（1<n<32768），表示会员人数。

Output
输出：对于每一个N，输出一行新朋友的人数，这样共有CN行输出。

Sample Input
2
25608
24027
Sample Output
7680
16016

#include<bits/stdc++.h>
using namespace std;
long long a[20],b[20];
long long gs;
int Aoligei(int x,int y);
int main()
{long long n,i,j,k,x,z,ans;scanf("%lld",&x);for(k=1;k<=x;k++){scanf("%lld",&n);z=n;ans=1;for(i=2;i<=n;i++){gs=0;while(n%i==0){n/=i;gs++;}if(gs!=0){ans*=Aoligei(i,gs-1)*(i-1);}}cout<<ans<<endl;}return 0;
}
int Aoligei(int x,int y)
{int i,z;z=1;for(i=1;i<=y;i++){z*=x;}return z;
}

这篇关于国赛集训-AOJ-分解篇的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---