1,分数拆分
时间限制：3000 ms | 内存限制：65535
难度：1
链接：Click here
描述
现在输入一个正整数k,找到所有的正整数x>=y,使得1/k=1/x+1/y.
输入
第一行输入一个整数n,代表有n组测试数据。
接下来n行每行输入一个正整数k
输出
按顺序输出对应每行的k找到所有满足条件1/k=1/x+1/y的组合
样例输入
2
2
12 样例输出
1/2=1/6+1/3
1/2=1/4+1/4
1/12=1/156+1/13
1/12=1/84+1/14
1/12=1/60+1/15
1/12=1/48+1/16
1/12=1/36+1/18
1/12=1/30+1/20
1/12=1/28+1/21
1/12=1/24+1/24 数学分析。
1) 我们假设 m <= n ，因为 k 必然小于 m 和 n ，则有 k < m <= n
2) 1/k=1/m+1/n 转换为 n 的等式，为 n = km/(m-k)
3) k 为输入，是已知数。我们要枚举 m 来获得 n 。
因为 k < m <= n ，也就是 k < m <= km/(m-k) ，解得 k < m <= 2k 。
4） 因此我们程序要做的就是：
枚举 m 的值为 [k+1,2k] 的一个【整数】，n = km/(m-k)
看是否能得到【整数解 n】
代码：
<span style="font-size:14px;">#include<stdio.h>
int main()
{
int s,n,i;
scanf("%d",&s);
while(s--)
{
scanf("%d",&n);
for(i=n+1; i<=2*n; ++i)
if(n*i%(i-n)==0)
printf("1/%d=1/%d+1/%d\n",n,n*i/(i-n),i);
}
}
</span> 2,除法
输入正整数n，按从小到大的顺序输出所有形如abcde / fghij = n的表达式，其中a~j恰好为0~9的一个排列，2<=n<=79.
样例输入：62
样例输出： 79546 / 01283 =62
94736 / 01528 =62
分析： 枚举0~9的所有排列？没这个必要。只需要枚举fghij就可以算出abcde，然后判断是否所有数字都不相同即可。不仅程序简单，而且枚举量也从10!=3628800降低至不到1万。
<span style="font-size:14px;">#include<stdio.h>
#include<string.h>
int main()
{
int i,j,n,s1,s2,flag[10];
while(~scanf("%d",&n))
{
for(i=1234;i<5000;i++)
{
memset(flag,0,sizeof(flag));
/*flag保存每一位数字*/
s1=i;
s2=i*n;
while(s1||s2)
{
if(!flag[s1%10])
{
flag[s1%10]=1;
s1/=10;
}
else
break;
if(!flag[s2%10])
{
flag[s2%10]=1;
s2/=10;
}
else
break;
}
for(j=0;j<10;j++)
if(!flag[j])
break; /*判断是否是10个各不相同的数字*/
if(j==10&&i*n<=98765) /*如果数字各不相同*/
{
if(i<10000) /*除数是一个四位数，有前导0*/
printf("%d / 0%d = %d\n",i*n,i,n);
else
printf("%d / %d = %d\n",i*n,i,n);
}
}
}
</span> 3、最大乘积
输入n个元素组成的序列s，你需要找出一个乘积最大的的连续子序列。如果这个最大的的乘积不是正数，输出-1.1<=n<=18,-10<=Si<=10;
样例输入：
3
2 4 -3
5
2 5 -1 2 -1
样例输出：
8
20
分析：连续子序列有两个要素：起点和终点，因此只需枚举起点和终点即可。由于每个元素的绝对值不超过10，一共又不超过18个元素，最大可能的乘积不会超过10^18，可以用long long 存下。
<span style="font-size:14px;">//普通方法超时
#include<stdio.h>
#include<string.h>
int main()
{
int n,m,i,j;
while(~scanf("%d",&n))
{
long long a[100000],b;
long long cnt,ans=1;
for(i=0; i<n; i++)
{
// //scanf("%lld",&a[i]);
// scanf("%d",&a);
// ans=ans*a;
// ///cnt=ans;
// if(ans>=a)
// {
// scanf("%d",&b);
//
// }
// continue;
// else
scanf("%lld",&a[i]);
}
long long M=0;
for(i=0; i<n; i++)
{
ans*=a[i];
if(M<ans)
M=ans;
}
printf("%lld\n",M);
}
}*/
//另外用一个数组存放上次乘积的结果,
#include<stdio.h>
#include<string.h>
const int inf=999999;
int main()
{
long long a[20],s[20];
long long i,j,n,max;
while(~scanf("%lld",&n))
{
memset(s,0,sizeof(s));
s[0]=1;
max=-inf;
for(i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
s[i]=s[i-1]*a[i];
/*s[i]表示从第一个数到第i个数的乘积*/
}
for(i=1;i<=n;i++) /*子序列长度*/
{
for(j=i;j<=n;j++)
{
if(s[j]/s[j-i]>max)
max=s[j]/s[j-i];
}
}
if(max<0)
max=-1;
printf("%lld\n",max);
}
return 0;
}
</span> 4、双基回文数
如果一个正整数n至少在两种不同的进制下b1和b2下都是回文数（2<=b1,b2<=10),则称n是双基回文数（注意，回文数不能包含前导零）。输入正整数S<10^6,输出比S大的最小的双基回文数。
样例输入： 1600000
样例输出： 1632995
分析：最自然的想法就是：从n+1开始依次判断每个数是否为双基回文数，而在判断时枚举所有可能的基数（2~10),一切都是那么的“暴力”。令人有些意外的是：这样做对于S<10^6这样的“小规模数据”来说是足够快的——双基回文数太多太密了。
代码：
<span style="font-size:14px;">#include<cmath>
#include<ctime>
#include<queue>
#include<stack>
#include<string>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
#define Max(a,b) a>b?a:b
#define Min(a,b) a>b?b:a
#define mem(a,b) memset(a,b,sizeof(a))
int dir[4][2]= {{0,-1},{-1,0},{0,1},{1,0}};
int a[50];
int huiwen(int s[],int n)/*判断是否回文*/
{
int i;
for(i=0; i<=n/2; i++)
{
if(a[i]!=a[n-i])
{
return 0;
break;
}
}
return 1;
}
int converse(int n,int k)/*把十进制的n转化为k进制*/
{
int flag=0,i,j=0;
while(n)
{
a[j++]=n%k;
n/=k;
}
if(huiwen(a,j-1))/*n在k进制下是回文数*/
flag=1;
if(flag) return 1;
else return 0;
}
int main()
{
int i,j,k,n,cnt;
while(~scanf("%d",&n))
{
for(j=n+1;; j++)
{
int p=0;
for(i=2,cnt=0; i<10; i++)
{
if(converse(j,i))
{
cnt++;/*记录回文次数*/
}
if(cnt>=2)/*是双基回文数*/
{
p=1;
break;
}
}
if(p)
{
printf("%d\n",j);
break;
}
}
}
return 0;
}
</span> ![POJ 1284 Primitive Roots (欧拉函数&原根定理)[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)