A：首先将p和q约分。容易发现相当于要求存在k满足bk mod q=0，也即b包含q的所有质因子。当然不能直接分解质因数，考虑每次给q除掉gcd(b,q)，若能将q除至1则说明合法。但这个辣鸡题卡常，每求一次gcd都除干净就可以了。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
char getc(){char c=getchar();while ((c<‘A‘||c>‘Z‘)&&(c<‘a‘||c>‘z‘)&&(c<‘0‘||c>‘9‘)) c=getchar();return c;}
ll gcd(ll n,ll m){return m==0?n:gcd(m,n%m);}
ll read()
{
ll x=0,f=1;char c=getchar();
while (c<‘0‘||c>‘9‘) {if (c==‘-‘) f=-1;c=getchar();}
while (c>=‘0‘&&c<=‘9‘) x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n;
ll p,q,b;
signed main()
{
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
n=read();
while (n--)
{
p=read(),q=read(),b=read();
q/=gcd(p,q);
ll u=gcd(b,q);
while (u>1&&q>1)
{
while (q%u==0) q/=u;
u=gcd(b,q);
}
if (q==1) puts("Finite");else puts("Infinite");
}
return 0;
//NOTICE LONG LONG!!!!!
}
B：先考虑求出每个区间的f值。可以发现若区间长度为x，对于区间内第i个元素，其对最后答案是否产生贡献仅与C(x,i)是否为奇数有关。直接计算仍然是O(n3)的，由于C(i,j)=C(i-1,j-1)+C(i-1,j)，f值我们也可以类似地递推得到，即f[i][j]=f[i+1][j]^f[i][j-1]，考虑其中每个元素被计算的次数容易证明。然后再预处理正方形最大值，同样递推一下即可。于是就O(1)回答询问了。
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<algorithm>
using namespace std;
#define ll long long
#define N 5010
char getc(){char c=getchar();while ((c<‘A‘||c>‘Z‘)&&(c<‘a‘||c>‘z‘)&&(c<‘0‘||c>‘9‘)) c=getchar();return c;}
ll gcd(ll n,ll m){return m==0?n:gcd(m,n%m);}
ll read()
{
ll x=0,f=1;char c=getchar();
while (c<‘0‘||c>‘9‘) {if (c==‘-‘) f=-1;c=getchar();}
while (c>=‘0‘&&c<=‘9‘) x=(x<<1)+(x<<3)+(c^48),c=getchar();
return x*f;
}
int n,q,a[N],f[N][N],ans[N][N];
signed main()
{
#ifndef ONLINE_JUDGE
freopen("b.in","r",stdin);
freopen("b.out","w",stdout);
#endif
n=read();
for (int i=1;i<=n;i++) a[i]=read();
for (int i=1;i<=n;i++) ans[i][i]=f[i][i]=a[i];
for (int i=2;i<=n;i++)
for (int j=1;j<=n-i+1;j++)
f[j][j+i-1]=f[j][j+i-2]^f[j+1][j+i-1];
for (int i=2;i<=n;i++)
for (int j=1;j<=n-i+1;j++)
ans[j][j+i-1]=max(max(ans[j][j+i-2],ans[j+1][j+i-1]),f[j][j+i-1]);
q=read();
for (int i=1;i<=q;i++)
{
int l=read(),r=read();
printf("%d\n",ans[l][r]);
}
return 0;
//NOTICE LONG LONG!!!!!
}
原文：https://www.cnblogs.com/Gloid/p/10416133.html