题目名称:大大大
Illyasviel:"两个数乘起来会比一个数大吗？"
Star-dust:"不知道啊，来算算吧。"
读入一个(n),对于一个三元组((i,j,k))满足要求当且仅当(1leq i,j,kleq n)且(i imes j geq k)。
输入描述:
一行一个数字(n)。
输出描述:
一行一个(ans)表示满足要求的三元组的个数。
输入样例:
10
输出样例:
900
数据范围:
对于30%的数据(nleq 100)
对于60%的数据(nleq 5000)
对于100%的数据(nleq 100000)
对于30%的做法
[思路]：n≤100,O(n³)即可满足需求，考虑分别枚举i,j,k并且判断这个是否满足要求
#include<iostream>
using namespace std;
int main()
{
int n;
long long ans;
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=1;k<=n;k++)
if(i*j>=k)
ans++;
cout<<ans;
}
对于60%的做法
[思路]：n≤5000,考虑对于一组确定的i,j,满足要求的k为min(n,k)。考虑枚举i,j在O(1)的时间内求一个可行区间。在O(n²)的时间里才能解决问题。
复杂度是n/1+n/2+n/3--
#include<iostream>
using namespace std;
int main()
{
int n;
long long ans;
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(i*j<=n)ans+=i*j;
else
{
ans+=n*(n-j+1);
break;
}
cout<<ans<<endl;
}
100分做法
[思路]：n≤100000
我们来反向考虑有多少个不满足要求的三元组，即i*j<k
那么我们考虑将(i,j)插入i*j+1中，然后求一个前缀和即可。
复杂度分析:i*j>n时可直接break。
对于一个有对于一个i有
个满足要求的j使得i*j<n总有效点对个数
约等于
#include<bits/stdc++.h>
#define N 120000
using namespace std;
long long a[N];
long long b[N];
long long ans=0;
long long n;
int main(){
//freopen("1.in","r",stdin);
//freopen("1.out","w",stdout);
scanf("%lld",&n);
for(int i=1;i<=n;i++){
for(int j=1;j<=n/i;j++){
a[j*i]++;
}
}
for(int i=1;i<=n;i++)b[i]=b[i-1]+a[i-1];
for(int i=1;i<=n;i++)ans+=b[i];
printf("%lld
",n*n*n-ans);
}
题目名称:kkk
Star-dust:"你会最短路吗？"
Illyasviel:"当然！"
Star-dust:"那你来求一求这k个点中是否存在长度%P为L的路径吧。"
Illyasviel:"这和最短路有什么关系吗?"
Star-dust:"不知道啊~"
输入描述:
第一行一个数字$T$代表数据组数。
对于每个数据，第一行三个数$n,m,k,P,L$表明有$n$个点，$m$条边，$k$个在图中的点。
接下来一行k个数代表关键点。
接下来$m$行每行三个数$x,y,z$表示$x$和$y$之间有一条长度为$z$的路径。
输出描述:
输出T行，当存在一条路径从起点和终点都在k个点中输出"YES",否则输出"NO"（不包含引号）。
输入样例:
1
2 3 2 3
1 2 1
2 1 1
输出样例:
YES
样例解释:
1-2-1-2
数据范围:
对于40%的范围(Tleq 500,0leq L,zleq Pleq 20,kleq nleq mleq 500,kleq 10)
对于80%的范围(Tleq 500,0leq L,zleq Pleq 20,kleq nleq mleq 500)
对于100%的范围(Tleq 500,0leq L,zleq Pleq 10^9,kleq nleq mleq 500),(P)是奇数。
100分做法
#include<bits/stdc++.h>
using namespace std;
int gcd(int x,int y){
/* if(y==0){
y++,y--;
return 0;
}*/
if(x%y==0)return y;
return gcd(y,x%y);
}
int solve(){
int n,m,k,P,L;
scanf("%d%d%d%d%d",&n,&m,&k,&P,&L);
for(int i=1;i<=k;i++){
int x;
scanf("%d",&x);
}
if(L==0)L=P;
int A=P,B=P;
for(int i=1;i<=m;i++){
int x,y,z;
scanf("%d%d%d",&x,&y,&z);
if(z==0){
z=P;
}
A=gcd(A,z);
}
B=gcd(B,L);
if(B%A==0)printf("YES
");
else printf("NO
");
}
int main(){
int T;
freopen("kkk10.in","r",stdin);
freopen("kkk10.out","w",stdout);
scanf("%d",&T);
while(T--)solve();
}
题目名称:A的B次方
题目描述:
Illyasviel:"今天我们学了(A^B)?"
Star-dust:"我们也学了诶！"
Star-dust:"那我来考考你吧！"
已知A和P，求一个任意的B使得(A^B≡B^A(mod P))
输入描述
一行输入两个整数(A)和(P)。
输出描述
输出任意一个满足要求的数字(B)。
(B)要为一个不大于(10^{18})的正整数。
样例输入
78 100
样例输出
16
数据范围
对于30%的数据:
(1leq A,Pleq 1000)
对于30%的数据:
(P)为质数
对于100%的数据:
(64leq Aleq 10^9)
(Pleq 10^9)
(1leq Bleq10^{18})
#include<bits/stdc++.h>
using namespace std;
long long A,P;
long long phi(long long x){
long long ans=1;
for(long long i=2;i*i<=x;i++){
if(x%i==0)ans*=(i-1),x/=i;
while(x%i==0)x/=i,ans*=i;
}
return ans*max(x-1,1LL);
}
long long power(long long x,long long k,long long P){
long long ans=1;
x%=P;
while(k){
if(k&1)(ans*=x)%=P;
(x*=x)%=P;
k>>=1;
}
return ans;
}
int main(){
scanf("%lld%lld",&A,&P);
long long B=A+P*phi(P);
printf("%lld
",B);
return 0;
// scanf("%lld
",&P);
// printf("%lld %lld
",P,phi(P));
// return 0;
printf("%lld %lld
",power(A,B,P),power(B,A,P));
}
题目名称：灯塔
Star-dust:"每个人都是灯塔，灯塔之间相隔万里，无法触碰无法沟通，唯一能做的就是用自己的光去照耀别人。"
Illyasviel:"如果能被某个灯塔一直照耀，那一定很幸福吧。"
Star-dust:"我能成为你的灯塔吗？"
Illyasviel:"好啊~"
海上有着(n)个灯塔，第(i)个灯塔在位置(i)闪耀着,灯塔的光覆盖着([i-d_i,i+d_i])的所有灯塔，对于第(k)个灯塔，他想知道有多少个(i)满足(i<k)且至少存在一个在(i)和(k)中间的灯塔(j)满足灯塔(j)同时被灯塔(i)和灯塔(k)照耀，并且(j)和(k)的距离小于等于(j)和(i)之间的距离。
输入描述：
第一行一个整数(n)。
接下来一行(n)个数字，第(i)个代表(d_i)。
输出描述：
一行一个答案(ans)。
(f_k)表示对于第(k)个灯塔有多少个灯塔满足条件。
(ans)为n个(f_k)的异或和。
样例输入：
10
2 2 3 2 3 2 3 3 3 1
样例输出：
2
样例解释：
对应位置答案分别为0 0 1 2 3 3 3 4 4 2
数据范围:
对于20%的数据:(nleq 100)
对于20%的数据:(nleq5000)
对于20%的数据:(di)完全相同
对于20%的数据:(nleq 100000)
对于100%的数据:(nleq 3000000),(1 leq d_ileq n)
#include<bits/stdc++.h>
#define N 3200000
#define lowbit(x) ((x)&-(x))
using namespace std;
int n,d[N],f[N];
int ans;
vector<int>a[N];
int t[N];
namespace bit{
int t[N];
int insert(int x,int a){
x=n-x+1;
for(int i=x;i<=n;i+=lowbit(i))t[i]+=a;
return 0;
}
int query(int x){
x=n-x+1;
int ans=0;
for(int i=x;i;i-=lowbit(i))ans+=t[i];
return ans;
}
}
inline int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
};
int main(){
//freopen("beacon.in","r",stdin);
//freopen("beacon.out","w",stdout);
n=read();
for(int i=1;i<=n;i++)d[i]=read();
for(int k=3;k<=n;k++){
int i=k-2;
int j=i+d[i];
int l=2*j-i+1;
l=min(l,n+1);
a[l].push_back(j);
bit::insert(min(j,n),1);
for(int o=0;o<a[k].size();o++){
bit::insert(min(a[k][o],n),-1);
}
f[k]=bit::query(max(k-d[k],1));
}
// for(int i=1;i<=n;i++)printf("%d ",f[i]);
// printf("
");
// return 0;
for(int i=1;i<=n;i++)ans^=f[i];
printf("%d
",ans);
}