T1：问题 A: Prime Distance
题目描述
给定两个整数 L,R，求闭区间 [L,R] 中相邻两个质数差值最小的数对与差值最大的数对。当存在多个时，输出靠前的素数对。
输入
多组数据。每行两个数 L,R。
输出
详见输出样例。
样例输入
2 17
14 17
样例输出
2,3 are closest, 7,11 are most distant.
There are no adjacent primes.
提示
【数据范围与提示】
对于全部数据，1≤L
题解：
由于数据保证在int范围，因此首先找质数，范围只用到就行。然后用一个数组来存这个数是否是质数。注意，数组开不到那么大，所以只用记录编号即可。然后不要对于每一个数去搜能否被质数整除，直接找这些质数的大的倍数，然后标记为合数，最后剩下的一定是大质数。然后直接找质数的距离，最后输出答案就可以了。（暴力出奇迹！！）
参考代码：
#include
#include
#include
#define LL long long
using namespace std;
LL prime[271000],cnt=0,mf[271000],l,r,f[1271000];
bool check(LL k)
{
LL ph=1,st=sqrt(k);
for(int j=1;j<=cnt&&prime[j]<=st;j++)
{
if(k%prime[j]==0)
{
ph=0;break;
}
}
return ph;
}
int main()
{
register LL i;
for(i=2;i<=100005;i++)
{
if(!mf[i])
{
mf[i]=i;
prime[++cnt]=i;
}
for(LL j=1;j<=cnt&&i*prime[j]<100005;j++)
{
mf[i*prime[j]]=prime[j];
if(mf[i*prime[j]]==mf[i]) break;
}
}
while(scanf("%lld%lld",&l,&r)!=EOF)
{
LL mins=999999999ll,maxs=0,pd=0,st=0;
LL min_l,min_r,max_l,max_r,pre=0;
if(l==1) l++;
memset(f,0,sizeof(f));
for(i=1;i<=cnt;i++)
{
int a=(l-1)/prime[i]+1;
int b=r/prime[i];
for(LL j=a;j<=b;j++)
{
if(j<=1) continue;
f[j*prime[i]-l]=1;
}
}
for(i=l;i<=r;i++)
{
if(f[i-l]) continue;
if(pre==0) pre=i;
else
{
if(i-premaxs)
{
maxs=i-pre;
max_l=pre;
max_r=i;
}
}
pre=i;
}
if(mins!=999999999&&maxs!=0)
printf("%d,%d are closest, %d,%d are most distant.n",min_l,min_r,max_l,max_r);
else printf("There are no adjacent primes.n");
}
return 0;
}
T2：问题 F: 方程的解
题目描述
佳佳碰到了一个难题，请你来帮忙解决。对于不定方程 a1 +a2 +⋯+ak−1 +ak =g(x)，其中 k≥2 且 k∈N∗ ，x 是正整数，g(x)=xx mod 1000（即 xx 除以 1000 的余数），x,k 是给定的数。我们要求的是这个不定方程的正整数解组数。
举例来说，当 k=3,x=2 时，方程的解分别为：
输入
有且只有一行，为用空格隔开的两个正整数，依次为 k,x。
输出
有且只有一行，为方程的正整数解组数。
样例输入
3 2
样例输出
3
提示
【数据范围与提示】
对于 40% 数据，答案不超过 ；
对于全部数据，1≤k≤100,1≤x< ,k≤g(x)。
题解：
显而易见，这道题要打高精。关键是用不用“高（mo）精（gui）除”。首先用一个快速幂解决对1000取模。然后用放挡板（数学排列组合基础知识）的思想，相当于在个物品的空中放k-1个隔板，把物品分割成k份（也就是k个解）。因此就是。因此问题就转化成求一个组合数的值。
是否是一定要打高精除？根据定义，可以把乘积式写出来，然后用数组记录“每一项”。由于最后的答案一定是整数，因此分数线上面的元素与下面的元素一定可以完全约分，把下面的元素全部转化成1.所以直接O()暴力枚举，对于每一个分母上的数，一定能找到分子上的一些数把它约掉。最后用一个高精乘就可以解决本题。
参考代码：
#include
using namespace std;
int k,a[1001],b,x,st=0,tot=1;
struct node
{
long long s[2000];
};
node ret;
node change(int k)
{
node pt;
int len=0,k1=k;
while(k1)
{
len++;
k1/=10ll;
}
pt.s[0]=len;
for(int i=1;i<=len;i++)
{
pt.s[i]=k%10ll;
k/=10ll;
}
return pt;
}
node multiple(node p,node q)
{
node ht;
ht.s[0]=p.s[0]+q.s[0]+50ll;
for(int i=1;i<=ht.s[0];i++) ht.s[i]=0;
for(int i=1;i<=p.s[0];i++)
{
for(int j=1;j<=q.s[0];j++)
{
ht.s[i+j-1]+=p.s[i]*q.s[j];
ht.s[i+j]+=ht.s[i+j-1]/10ll;
ht.s[i+j-1]%=10ll;
}
}
for(int i=1;i<=ht.s[0];i++)
{
ht.s[i+1]+=ht.s[i]/10ll;
ht.s[i]%=10ll;
}
while(ht.s[ht.s[0]]==0) ht.s[0]--;
return ht;
}
int gcd(int a,int b)
{ return b==0?a:gcd(b,a%b); }
int qpow(int x,int y,int p)
{
int ret=1;
while(y)
{
if(y&1) ret=(ret*x)%p;
x=x*x%p;
y/=2;
}
return ret;
}
int main()
{
ret=change(1);
scanf("%d%d",&k,&x);
x=qpow(x%1000,x,1000);
if(x=x-(k-1);i--)
{
b=i;
for(int j=tot;j<=k-1;j++)
{
if(b==1) break;
if(a[j]==1) continue;
int gds=gcd(b,a[j]);
if(gds==1) continue;
b/=gds;a[j]/=gds;
}
while(a[tot]==1) tot++;
node rs,ts;
rs=change(b);
ts=multiple(ret,rs);
ret=ts;
}
for(int i=ret.s[0];i>=1;i--)
printf("%lld",ret.s[i]);
printf("n");
return 0;
}
