A-August
题意：
求给定曲线所包围的面积
solution：
求积分问题。但是好像数方格也能过。（x轴以下正好左半边能跟右半边能完整拼成一个矩形，x轴以上可以拼成一个圆）
∫ a r c s i n ( x ) d x = x a r c s i n x + 1 − x 2 + C \int{arcsin(x)dx=xarcsinx+\sqrt{1-x^2}+C} ∫arcsin(x)dx=xarcsinx+1−x2+C
这边只求右下部分面积，上部分就是半圆的组合，左下和右上面积相同。
S = ∫ 0 2 a 0 − 2 b π ( a r c s i n ( x − a a ) − π 2 ) d x = 2 a b − ∫ 0 2 a 2 b π a r c s i n ( x − a a ) d x = 2 a b S=\int^{2a}_0{0-\frac{2b}{\pi}(arcsin(\frac{x-a}{a})-\frac{\pi}{2})dx}=2ab-\int^{2a}_0\frac{2b}{\pi}arcsin(\frac{x-a}{a})dx=2ab S=∫02a0−π2b(arcsin(ax−a)−2π)dx=2ab−∫02aπ2barcsin(ax−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
题意：
给了 σ k ( n ) = ∑ d ∣ n d k \sigma_k(n)=\sum_{d|n}d^k σk(n)=∑d∣ndk的定义，求解
( ( ∑ i = 1 n σ a ( i ) ) ⊕ ( ∑ i = 1 n σ b ( i ) ) ) m o d 2 64 ((\sum_{i=1}^n\sigma_a(i))⊕(\sum_{i=1}^n\sigma_b(i)))mod \ 2^{64} ((∑i=1nσa(i))⊕(∑i=1nσb(i)))mod 264，给了a，b，n的值。
solution：
tips：关于模数为 2 64 2^{64} 264的取模问题，可以使用unsigned long long 的自然溢出进行取模。
异或和左右式子相同，所以这边只推导左边的式子。
∑ i = 1 n σ a ( i ) = ∑ i = 1 n ∑ i ∣ n i a = ∑ i = 1 n ⌊ n i ⌋ × i a \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=1nσa(i)=∑i=1n∑i∣nia=∑i=1n⌊in⌋×ia推导到这一步发现就是当i逐渐增大 ⌊ n i ⌋ \lfloor \frac{n}{i} \rfloor ⌊in⌋相同的次数出现的越来越多，感觉就可以转换到整除分块。对于相同的 ⌊ n i ⌋ \lfloor \frac{n}{i} \rfloor ⌊in⌋后面的 i a i^a ia可以通过幂和求解，虽然当时用了奇怪的方法（举证快速幂求解的，然后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;
}
京公网安备 11010502036488号