A
import random
import sys
import os
import math
from collections import Counter, defaultdict, deque
from functools import lru_cache, reduce
from itertools import accumulate, combinations, permutations
from heapq import nsmallest, nlargest, heapify, heappop, heappush
from io import BytesIO, IOBase
from copy import deepcopy
import bisect
# from sortedcontainers import SortedList
BUFSIZE = 4096
class FastIO(IOBase):
newlines = 0
def __init__(self, file):
self._fd = file.fileno()
self.buffer = BytesIO()
self.writable = "x" in file.mode or "r" not in file.mode
self.write = self.buffer.write if self.writable else None
def read(self):
while True:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
if not b:
break
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines = 0
return self.buffer.read()
def readline(self):
while self.newlines == 0:
b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
self.newlines = b.count(b"\n") + (not b)
ptr = self.buffer.tell()
self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
self.newlines -= 1
return self.buffer.readline()
def flush(self):
if self.writable:
os.write(self._fd, self.buffer.getvalue())
self.buffer.truncate(0), self.buffer.seek(0)
class IOWrapper(IOBase):
def __init__(self, file):
self.buffer = FastIO(file)
self.flush = self.buffer.flush
self.writable = self.buffer.writable
self.write = lambda s: self.buffer.write(s.encode("ascii"))
self.read = lambda: self.buffer.read().decode("ascii")
self.readline = lambda: self.buffer.readline().decode("ascii")
sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")
def I():
return input()
def II():
return int(input())
def MI():
return map(int, input().split())
def LI():
return list(input().split())
def LII():
return list(map(int, input().split()))
def GMI():
return map(lambda x: int(x) - 1, input().split())
def LGMI():
return list(map(lambda x: int(x) - 1, input().split()))
if __name__ == '__main__':
for _ in range(II()):
n=II()
a=LII()
mx=max(a)
mn=min(a)
cnt=Counter(a)
cha=mx-mn
if cha==0:
res = 0
for i in a:
x, y = i, i + cha
res += (cnt[y]-1)
print(res)
else:
res=0
for i in a:
x,y=i,i+cha
res+=cnt[y]
x,y=i,i-cha
res+=cnt[y]
print(res)
B
#include <iostream>
#include <cstring>
#include <algorithm>
#include <unordered_map>
using namespace std;
const int N = 2e5+10;
int n,m;
void solve(){
unordered_map<int,vector<int>> mp;
cin>>n>>m;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
mp[a].push_back(b);
mp[b].push_back(a);
}
int l=1,r=1;
long long res=0;
while(r<=n){
int x=r;
for(auto&s:mp[x])
{
if(s>r) continue;
if(s>=l)
{
l=s+1;
}
}
res+=r-l+1;
r++;
}
cout<<res<<endl;
}
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int t;
cin>>t;
while(t--){
solve();
}
}
C
#include <iostream>
#include <cstring>
#include <algorithm>
#include <map>
using namespace std;
const int N = 1e5+10;
#define endl '\n'
int cnt;
int st[N],primes[N];
int n;
int a[N];
map<int,int> c;
void count(int n){
st[1]=true;
for(int i=2;i<=n;i++){
if(!st[i]) primes[cnt++]=i;
for(int j=0;primes[j]<=n/i;j++){
st[primes[j]*i]=true;
if(i%primes[j]==0) break;
}
}
}
void solve(){
cin>>n;
c.clear();
for(int i=1;i<=n;i++)
{
cin>>a[i];
for(int j=0;j<cnt;j++)
{
if(a[i]%primes[j]==0) c[j]++;
while(a[i]%primes[j]==0) a[i]/=primes[j];
}
if(a[i]!=1) c[a[i]]++;
}
bool flag=false;
for(auto it:c){
if(it.second>=2) flag=true;
}
if(flag) puts("YES");
else puts("NO");
}
int main()
{
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(0);
int t;
//cout<<cnt;
count(50000);
cin>>t;
while(t--){
solve();
}
}
D
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
const int N = 2e3+10;
#define endl '\n'
vector<int> e[N];
char s[N];
int f[N][N],nxt[N][N];
void dfs(int u,int fa,int from,int to){
nxt[from][u]=to;
// cout<<from<<" "<<to<<endl;
for(int v:e[u]){
if(v==fa) continue;
dfs(v,u,from,to);
}
}
int dp(int x,int y){
if(f[x][y]!=-1) return f[x][y];
f[x][y]=0;
if(nxt[x][y]==y&&nxt[y][x]==x)
return f[x][y]=f[y][x]=(s[x]==s[y]?2:1);
if(s[x]==s[y]) return f[x][y]=2+dp(nxt[x][y],nxt[y][x]);
return f[x][y]=max(dp(x,nxt[y][x]),dp(y,nxt[x][y]));
}
void solve(){
int n,ans=1;
scanf("%d%s",&n,s+1);
memset(f,-1,sizeof(f));
for(int i=1;i<=n;i++){
e[i].clear();
f[i][i]=1;
}
for(int i=1;i<n;i++){
int u,v;
scanf("%d%d", &u, &v);
e[u].push_back(v);
e[v].push_back(u);
}
for(int u=1;u<=n;u++)
for(int v:e[u]) dfs(v,u,u,v);
for(int i=2;i<=n;i++){
for(int j=1;j<i;j++)
ans=max(ans,dp(i,j));
}
cout<<ans<<endl;
}
int main()
{
int t;
scanf("%d", &t);
while(t--) solve();
}