ACM-ICPC 2018 南京赛区网络预赛 题解（未完）
发布时间
阅读量：
阅读量
目录
A.An Olympian Math Problem【签到题】
J.Sum【分解质因数+线性筛】
A.An Olympian Math Problem【签到题】
题意：
给你一个n
求S模n的值
题解：推规律
AC_code:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
int main() {
int t;
scanf("%d", &t);
while(t--) {
ll n;
cin>>n;
cout<<n-1<<endl;
}
return 0;
}J.Sum【分解质因数+线性筛】
题意：给你一个数n
f（n）为 定义ab = n 且 a和b不为某个数的平方数的倍数 的对数 且ab=n 与 b*a=n为两对
求 f（1）.....f （n）的和
题解：
唯一分解 x
f(x)就是2^k，其中k是x分解结果中次数为一的质因子个数。如果有某个次数大于等于3，f(x)==0;
如果每个数都去枚举一遍求会tle 所以通过线性筛改一下就不会tle了
AC_code:
#include<bits/stdc++.h>
using namespace std;
const int maxn = 20100000;
typedef long long ll;
int num = 0;
int vis[maxn], pri[maxn];
ll f[maxn], s[maxn];
void init() {
for(int i = 0; i < maxn; i++) {
f[i] = 1;
}
memset(vis, 0, sizeof(vis));
memset(pri, 0, sizeof(pri));
num = 0;
}
void getpri() {
for(int i = 2; i < maxn; i++) {
if(!vis[i]) {
pri[++num] = i;
f[i] = 2;
}
for(int j = 1; j <= num && pri[j] * i < maxn; j++) {
vis[pri[j] * i] = 1;
f[pri[j] * i] *= f[pri[j]] * f[i];
if(i % pri[j] == 0) {
f[pri[j] * i] /= 4;
if(i % (pri[j] * pri[j]) == 0) {
f[pri[j] * i] = 0;
}
break;
}
}
}
}
void solve() {
getpri();
s[1] = 1;
for(int i = 2; i < maxn; i++){
s[i] = s[i-1] + f[i];
}
int t;
cin>>t;
while(t--) {
int n;
cin>>n;
cout<<s[n]<<endl;
}
}
int main() {
init();
solve();
return 0;
}全部评论 (0)
还没有任何评论哟~