Tasks - AtCoder Beginner Contest 254

D - Together Square

题意: 给定一个N，找出所有不超过N的 ( i , j )，使得( i * j )是一个平方数。

题解: 首先要知道一个数学只是，如果i*j是平方数，那么i*j /(f(i)*f(j))也是平方数  (f(j)表示的是j的不超过j的最大平方数因子)，然后因为i/f(i)一定可以被质数 p分割两次或更多，所以得到 i/f(i)=j/f(j))

#include
using namespace std;
typedef long long ll;
typedef pair pll;
const int N=2e5+10;
const ll mod=1e9+7;
vector p,q;
ll n,t,cnt[N];
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n;
for(ll i=1;i*i<=n;i++){
p.push_back(i*i);
}
for(ll i=1;i<=n;i++){
ll f=*(upper_bound(p.begin(),p.end(),i)-1);//找到不超过i的最大的平方数
if(i%f!=0){
ll d=(ll)sqrt(f);
while(i%f!=0){//判断是不是i的因子，不是就减
d--;
f=d*d;
}
}
cnt[i/f]++;
}
ll ans=0;
for(ll i=1;i<=n;i++) ans+=cnt[i]*cnt[i];
cout<<ans;
}

E - Small d and k

题意: 一个无向图，每次询问一个点，与这个点距离不超过k的所有点的权值之和

题解: 暴力即可，注意每次vis的清零，不要用memset全部清零，会tle，可以存储一下所有走过的点，然后最后只将他们清空。

#include
using namespace std;
typedef long long ll;
typedef pair pll;
const int N=3e5+5;
const ll mod=998244353;
const ll inf=1e18;
ll n,dp[N],m;
ll cnt,head[N*2],ans,vis[N];
struct ss{
ll next,to;
}e[N*2];
void add(ll x,ll y){
e[++cnt].to=y;
e[cnt].next=head[x];
head[x]=cnt;
}
void bfs(ll beg,ll maxn){
queue q;
q.push({beg,0});
vis[beg]=1;
vector sum;
sum.push_back(beg);
while(!q.empty()){
ll l=q.front().first;
ll r=q.front().second;
q.pop();
if(r<=maxn) ans+=l; else continue; for(ll i=head[l];i;i=e[i].next){ ll j=e[i].to; if(!vis[j]) vis[j]=1,sum.push_back(j),q.push({j,r+1}); } } for(ll i=0;i>n>>m;
for(ll i=1;i<=m;i++){ ll x,y;cin>>x>>y;
add(x,y); add(y,x);
}
ll t;cin>>t;
while(t--){
ll x,y;cin>>x>>y;
ans=0;
bfs(x,y);
cout<<ans<<endl;
}
}