zjnu_12_13

zjnu_12_13

A-August

题意：

求给定曲线所包围的面积

solution：

求积分问题。但是好像数方格也能过。（x轴以下正好左半边能跟右半边能完整拼成一个矩形，x轴以上可以拼成一个圆）
$\int arcsin(x)dx=xarcsinx+\sqrt{1-x^2}+C$
这边只求右下部分面积，上部分就是半圆的组合，左下和右上面积相同。
$S={\int }_0^{2a}0-\frac{2b}{\pi }(arcsin(\frac{x-a}{a})-\frac{\pi }{2})dx=2ab-{\int }_0^{2a}\frac{2b}{\pi }arcsin(\frac{x-a}{a})dx=2ab$

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
typedef pair<int,int>P;
const double PI=acos(-1);
int t,a,b;

int main()
{
   
    scanf("%d",&t);
    while(t--)
    {
   
        scanf("%d%d",&a,&b);
        double res=PI*a*a+4*a*b;
        printf("%.8f\n",res);
    }
    return 0;
}

B-Bills of Paradise

C-Cornelia Street

D-Death by Thousand Cuts

E-Everybody Lost Somebody

F-False God

G-Goodbye

题意：

给了一个数，每个人轮流阐述，一个人阐述真因子，另一个人阐述前面一轮那个人阐述的数的真因子，到最后谁不能阐述谁赢。（真因子指出了1和本身外的其他因子）问Chino最大能阐述的真因子是什么。输出0或最大真因子，如果直接能赢，如果不能赢输出-1。

solution：

输出最大的两个素数相乘。如果有多于两个的素数，只有一个素数因子输出-1，否则输出0。

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
typedef pair<int,int>P;
typedef unsigned long long ull;
int t;
int n;
int prime[100005],cnt=0;
int vis[100005];
int main()
{
   
    for(int i=2;i<=100000;i++)
    {
   
        if(!vis[i])
        {
   
            prime[cnt++]=i;
            for(int j=i*2;j<=100000;j+=i)
                vis[j]=1;
        }
    }
    scanf("%d",&t);
    while(t--)
    {
   
        scanf("%d",&n);
        int res=1;
        int c=0;
        if(vis[n]==0)
            printf("0\n");
        else
        {
   
            for(int i=cnt-1;i>=0;i--)
            {
   
                if(prime[i]>n)continue;
                while(n%prime[i]==0)
                {
   
                    if(n/prime[i]==1)break;
                    c++;
                    res*=prime[i];
                    n/=prime[i];
                    if(c==2)break;
                }
                if(c==2)break;
            }
            if(c<=1)
                printf("-1\n");
            else if(c==2)
                printf("%d\n",res);
        }
    }
    return 0;
}

H-Hate That You Know Me

题意：

给了${\sigma }_k(n)={\sum }_{d|n}{d}^k$的定义，求解
$(({\sum }_{i=1}^n{\sigma }_a(i))\oplus ({\sum }_{i=1}^n{\sigma }_b(i)))mod{2}^{64}$，给了a，b，n的值。

solution：

tips：关于模数为$2^{64}$的取模问题，可以使用unsigned long long 的自然溢出进行取模。

异或和左右式子相同，所以这边只推导左边的式子。
${\sum }_{i=1}^n{\sigma }_a(i)={\sum }_{i=1}^n{\sum }_{i|n}{i}^a={\sum }_{i=1}^n\lfloor \frac{n}{i}\rfloor \times i^a$推导到这一步发现就是当i逐渐增大$\lfloor \frac{n}{i}\rfloor$相同的次数出现的越来越多，感觉就可以转换到整除分块。对于相同的$\lfloor \frac{n}{i}\rfloor$后面的$i^a$可以通过幂和求解，虽然当时用了奇怪的方法（举证快速幂求解的，然后tle，就优化了部分（前面的数没有用矩阵快速幂，而是直接暴力求解，卡过去了））。

矩阵快速幂+数论分块

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
typedef pair<int,int>P;
typedef unsigned long long ull;
int a,b;
ll n;
ull res1=0,res2=0;
struct martix
{
   
    ull a[6][6];
}num[5][64];
martix cheng(martix x,martix y)
{
   
    martix ans;
    for(int i=0;i<=4;i++)
        for(int j=0;j<=4;j++)
            ans.a[i][j]=0;
    for(int i=0;i<=4;i++)
    {
   
        for(int j=0;j<=4;j++)
        {
   
            for(int k=0;k<=4;k++)
            {
   
                ans.a[i][j]=(ans.a[i][j]+x.a[i][k]*y.a[k][j]);
            }
        }
    }
    return ans;
}
ull ppow(ull ti,ull x)
{
   
    ull ans=1;
    while(ti)
    {
   
        if(ti&1)ans*=x;
        x*=x;
        ti>>=1;
    }
    return ans;
}
ull fpow(ll ti,int m,ll l,ll r)
{
   
    if(ti<=230)
    {
   
        ull ans=0;
        for(ll i=l;i<=r;i++)
            ans+=ppow(m,i);
        return ans;
    }
    martix p,tem;
    for(int i=0;i<=4;i++)
        for(int j=0;j<=4;j++)
            p.a[i][j]=tem.a[i][j]=0;
    p.a[0][0]=p.a[1][1]=p.a[1][4]=p.a[2][2]=p.a[2][4]=p.a[3][3]=p.a[3][4]=p.a[4][4]=1;
    p.a[1][2]=p.a[1][3]=3;
    p.a[2][3]=2;
    p.a[0][4-m]=1;
    for(int i=0;i<=4;i++)
        tem.a[i][i]=1;
    int cnt=0;
    while(ti)
    {
   
        if(ti&1)tem=cheng(tem,num[4-m][cnt]);
        ti>>=1;
        cnt++;
    }
    ull ans=0;
    ans=(tem.a[0][1]*l*l*l+tem.a[0][2]*l*l+tem.a[0][3]*l+tem.a[0][4]);
    return ans;
}
void solve(int m)
{
   
    martix p;
    for(int i=0;i<=4;i++)
        for(int j=0;j<=4;j++)
            p.a[i][j]=0;
    p.a[0][0]=p.a[1][1]=p.a[1][4]=p.a[2][2]=p.a[2][4]=p.a[3][3]=p.a[3][4]=p.a[4][4]=1;
    p.a[1][2]=p.a[1][3]=3;
    p.a[2][3]=2;
    p.a[0][4-m]=1;
    num[4-m][0]=p;
    for(int i=1;i<64;i++)
        num[4-m][i]=cheng(num[4-m][i-1],num[4-m][i-1]);
}
int main()
{
   
    scanf("%d%d%lld",&a,&b,&n);
    //clock_t start,finish;
    //start=clock();
    //n=1000000000000;a=3;b=3;
    if(a==b)return printf("0")*0;
    solve(a);
    solve(b);
    ll cnt=0;
    for(ll l=1,r;l<=n;l=r+1)
    {
   
        if(n/l)r=n/(n/l);
        else r=n;
        r=min(r,n);
        res1=(res1+fpow(r-l+1,a,l,r)*(n/l));
        res2=(res2+fpow(r-l+1,b,l,r)*(n/l));
    }
    res1=(res1^res2);
    printf("%llu",res1);
   // finish=clock();
    //double Total_time=(double)(finish-start)/CLOCKS_PER_SEC;
    //printf("\n%f",Total_time);
    return 0;
}

数论分块+幂和

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef long long ll;
typedef pair<int,int>P;
typedef unsigned long long ull;
int a,b;
ll n;
ull res1=0,res2=0;
ull gcd(ull a,ull b)
{
   
    return b?gcd(b,a%b):a;
}
ull getans(ll n,int m)
{
   
    if(m==0)
        return n;
    else if(m==1)
    {
   
        if(n%2==0)return 1ull*n/2*(n+1);
        else return 1ull*(n+1)/2*n;
    }
    else if(m==2)
    {
   
        ull a=n,b=n+1,c=2*n+1;
        ull chu=6;
        ull d=gcd(a,chu);
        a/=d;chu/=d;
        d=gcd(b,chu);
        b/=d;chu/=d;
        d=gcd(c,chu);
        c/=d;chu/=d;
        return a*b*c;
    }
    else if(m==3)
    {
   
        if(n%2==0)return 1ull*(n/2)*(n/2)*(n+1)*(n+1);
        else return 1ull*((n+1)/2)*((n+1)/2)*n*n;
    }
}
ull fpow(ll l,ll r,int m)
{
   
    return getans(r,m)-getans(l-1,m);
}
int main()
{
   
    scanf("%d%d%lld",&a,&b,&n);
    if(a==b)return printf("0")*0;
    for(ll l=1,r;l<=n;l=r+1)
    {
   
        if(n/l)r=n/(n/l);
        else r=n;
        r=min(r,n);
        res1=(res1+fpow(l,r,a)*(n/l));
        res2=(res2+fpow(l,r,b)*(n/l));
    }
    res1^=res2;
    printf("%llu",res1);
    return 0;
}

I-InkBall FX

J-Jingle Bells

K-Keeping A Secret

L-Let’s Get Married