J. Nanjing Sum
题目描述
A square-free integer is an integer which is indivisible by any square number except 1. For example, 6 = 2·3 is square-free, but 12 = 22·3 is not, because 22 is a square number. Some integers could be decomposed into product of two square-free integers, there may be more than one decomposition ways. For example, 6 = 1·6=6·1=2·3=3·2, n=ab and n=ba are considered different if a≠b. f(n) is the number of decomposition ways that n=ab such that a and b are square-free integers. The problem is calculating
.
输入
The first line contains an integer T(T≤20), denoting the number of test cases. For each test case, there first line has a integer n(n≤2·107).
输出
For each test case, print the answer
.
样例输入
2 5 8
样例输出
8 14
提示
=f(1)+⋯+f(8)=1+2+2+1+2+4+2+0=14
素数的f()一定是2
如果说对一个数x进行唯一分解之后，其某一项的指数≥ 3，那么说这个f()值一定是0
n=p1e1⋅x ，则有
为什么哩，因为如果 e1 = 2，那么对于 n ，pe1 的贡献就只有 1，p21= p 1 ⋅ p 1 ，所以 f ( p21) = 1 ，而当 e 1 = 1 时，贡献为2 ，因为此时p1 为质数， f ( p1 ) = 2 ，但是得同时保证 x和pe1 1没有大于x 和pe11没有大于1 的共同因子.
最后前缀和一下就可以完成了
可以参考：博客
bool vis[maxn]; int cnt = 0; int Pri[maxn]; ll f[maxn]; void _Get_Prime(int lim) { f[1] = 1LL; for (ll i = 2; i <= lim; i++) { if (vis[i] == 0) { Pri[++cnt] = i; f[i] = 2;///prime } for (ll j = 1; j <= cnt; j++) { ll val = i * Pri[j]; if(val > lim) break; vis[val] = 1; if (i % Pri[j]) f[val] = f[i] * f[Pri[j]]; else if(i % (Pri[j] * Pri[j]) == 0) { f[val] = 0; } else { f[val] = f[val / (Pri[j] * Pri[j])]; break; } } } } int main() { _Get_Prime(20000000); for(int i=1; i<=20000000; i++) { f[i] += f[i-1]; } int _ = read; while(_ --) { ll x = read; printf("%lld\n",f[x]); } return 0; } /** **/
L. Magical Girl Haze
题目描述
There are N cities in the country, and M directional roads from u to v(1<=u, v<=n).Every road has a distance ci. Haze is a Magical Girl that lives in City 1, she can choose no more than K roads and make their distances become 0. Now she wants to go to City N, please help her calculate the minimum distance.
输入
The first line has one integer T(1<=T<=5), then following T cases.
For each test case, the first line has three integers N, M and K. Then the following M lines each line has three integers, describe a road, Ui, Vi, Ci. There might be multiple edges between u and v.
It is guaranteed that N<=100000, M<=200000, K<=10, 0<=c[i]<=1e9. There is at least one path between City 1 and City N.
输出
For each test case, print the minimum distance.
样例输入
1 5 6 1 1 2 2 1 3 4 2 4 3 3 4 1 3 5 6 4 5 2
样例输出
3
题意：
从可以将图中不超过k条有向边的边权设置为0，然后问从1到n的最短路径是多少
可以用分层图最短路来实现
const int maxn=5e6+7; const int inf=0x3f3f3f3f; int T,n,m,k; int tot,head[maxn]; ll d[maxn]; bool f[maxn]; struct edge{ int to,next,w; }e[maxn]; struct node{ int dis,u; node(int dis,int u):dis(dis),u(u){}; bool operator<(const node &t)const{ return dis>t.dis; } }; void add(int u,int v,int w){ e[++tot].w=w; e[tot].to=v; e[tot].next=head[u]; head[u]=tot; } void dij(){ priority_queue<node>q; memset(f,0,sizeof(f)); memset(d,inf,sizeof(d)); d[0]=0; q.push(node(0,0)); while(!q.empty()){ node x=q.top(); q.pop(); int u=x.u,dis=x.dis; if(f[u]) continue; f[u]=1; for(int i=head[u];i;i=e[i].next){ int y=e[i].to; // cout<<y<<endl; if(d[y]>d[u]+e[i].w){ d[y]=d[u]+e[i].w; q.push(node(d[y],y)); } } } } int main(){ T=read(); while(T--){ n=read(); m=read(); k=read(); memset(head,0,sizeof(head)); tot=0; while(m--){ int u,v,w; u=read()-1; v=read()-1; w=read(); for(int i=0;i<=k;i++){ add(u*(k+1)+i,v*(k+1)+i,w); if(i<k) add(u*(k+1)+i,v*(k+1)+i+1,0); } } dij(); int sum=inf; for(int i=0;i<=k;i++) sum=min(1ll*sum,d[(n-1)*(k+1)+i]); cout<<sum<<endl; } } /* 1 5 6 1 1 2 2 1 3 4 2 4 3 3 4 1 3 5 6 4 5 2 */
![[计蒜客] ACM-ICPC 2018 南京赛区网络预赛 | 部分题解 | 线段树 + 线性筛 + 最短路（上）](https://ucc.alicdn.com/pic/developer-ecology/d3c2fdd70f4d439380a044791e251bd3.png?x-oss-process=image/resize,h_160,m_lfit)
