zoj 2013 Changsha Regional Online Contest C E G H J 题(三)
ime[i]==0)
{
int cnt=n/prime[i];
tmp+=multi[n/prime[i]]; // 同上
if(prime[i]*prime[i]*prime[i]==n)
tmp+=2;
else if(sq(cnt) && vis[int(sqrt(cnt+0.0))])
tmp++;
}
}
ans+=tmp/3;
printf("%d\n",ans);
}
return 0;
}
题目：H Hypersphere
矩阵快速幂，读懂题意就好做了
#include
#include
#include
#include
#include
using namespace std;
struct Matrix
{
long long m[3][3];
}E,D;
long long mod;
void init()
{
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
E.m[i][j]=(i==j);
}
Matrix Multi(Matrix A,Matrix B)
{
Matrix ans;
for(int i=1;i<=2;i++)
for(int j=1;j<=2;j++)
{
ans.m[i][j]=0;
for(int k=1;k<=2;k++)
ans.m[i][j]=(ans.m[i][j]+A.m[i][k]*B.m[k][j])%mod;
}
return ans;
}
Matrix Pow(Matrix A,long long k)
{
Matrix ans=E;
while(k)
{
if(k&1)
{
k--;
ans=Multi(ans,A);
}
else
{
k/=2;
A=Multi(A,A);
}
}
return ans;
}
int main()
{
init();
long long k,l;
while(scanf("%lld%lld",&k,&l)!=EOF)
{
mod=k;
Matrix ans;
ans.m[1][1]=l%mod;
ans.m[1][2]=l*(l-1)%mod;
ans.m[2][1]=1;
ans.m[2][2]=l%mod;
ans=Pow(ans,k);
printf("%lld\n",(ans.m[1][1]*2+mod-1)%mod);
}
return 0;
}
题目：J Candies
先考虑能否通过正向反向求出整个序列，不然的话就贪心，所有i%3==1的未知的在同一时刻取得最大值或者最小值，跟i%3==2的情况相反。
#include
#include
#include
#include
#include
using namespace std;
#define maxn 100010
int a[maxn],b[maxn];
int ans1[maxn],ans2[maxn];
bool ok;
void query()
{
int m,x;
scanf("%d",&m);
while(m--)
{
scanf("%d",&x);
x++;
if(ok || x%3==0)
{
printf("%d\n",a[x]);
}
else
{
if(x%3==1)
printf("%d\n",ans1[x]);
else
printf("%d\n",ans2[x]);
}
}
return ;
}
int main()
{
int n;
while(scanf("%d",&n)!=EOF)
{
int index=-1;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
if(a[i]!=-1 && i%3!=0)
index=i;
}
a[0]=0,a[n+1]=0;
ok=false;
for(int i=1;i<=n;i++)
scanf("%d",&b[i]);
for(int i=3;i<=n;i+=3) // 形如a[i%3==0]的项可以全部求出来
a[i]=b[i-1]-b[i-2]+a[i-3];
for(int i=n-2;i>=1;i-=3)
a[i]=b[i+1]-b[i+2]+a[i+3];
if((n-2)%3==1 || (n-2)%3==2)
{
for(int i=1;i<=n;i++)
if(a[i]==-1)
a[i]=b[i]-a[i-1]-a[i+1];
ok=1;
}
if(ok)
{
query();
continue;
}
if(index!=-1)
{ // 从index处推出所有的情况
if(index%3==1)
{
a[index+1]=b[index+1]-a[index+2]-a[index];
for(int i=index+3;i<=n;i++)
a[i]=b[i-1]-a[i-2]-a[i-1];
for(int i=index-1;i>=1;i--)
a[i]=b[i+1]-a[i+2]-a[i+1];
}
else if(index%3==2)
{
for(int i=index+2;i<=n;i++)