对所有数求gcd，然后结果乘上n。 using namespace std; #include <bits/stdc++.h> #define ll long long int main(){ int n; cin>>n; int g; cin>>g; for(int i=1;i<n;i++){ int v; cin>>v; g=gcd(g,v); } cout<<(ll)g*n<<endl; }

不用dijkstra也可以打表。最短路不必用dijkstra推出来，肯定是1直接走到n，这样二进制变化肯定是最少的（反正到最后肯定要变嘛）。然后再做一个前缀异或和，就可以打表了。不过，不打表直接推也行。相邻的偶数和奇数，2k与2k+1的异或和肯定是1。1->2 边权31->3 边权21->5 边权41->4 边权5n为奇数的时候比如n=5，1 2 3 4 5，可以看成1 （2 3）（4 5），结果分别是0 1 1，异或起来就是0。比如n=7，1 2 3 4 5 6 7，可以看成1 （2 3）（4 5）（6 7），结果分别是0 1 1 1，异或起来就是1。......依次...

注意到n<=1e3，对于一个无根树，令每一个点为根，然后分别做搜索（我采用BFS）。复杂度O（n^2）很合理。然后做BFS搜索，把当前结点与当前值扔到队列里面。如果访问到点为1，乘2加1（<<1|1）；如果访问到点为0，乘2（<<1）.但是交了一发竟然没过，哦！原来溢出了，做一个防溢出处理即可。 using namespace std; #include <bits/stdc++.h> #define ll long long #define ull unsigned long long #define PII pair<int,int> ...

就是做一个前缀积，pre[i]是前i项累乘。与前缀和类似，求出[l,r]区间的乘积可以表示为pre[r]/pre[l-1]，但是注意到这题有取模操作，所以除一个数需要转化为乘法逆元，所以查询结果就是pre[r]*inv(pre[l-1])。没见过乘法逆元的可以了解一下费马小定理等知识点。乘法逆元的计算是利用快速幂qpow的，快速幂可以将求x的n次方问题复杂度降到O（logn），这又是一个基础内容了。 using namespace std; #include <bits/stdc++.h> #define ll long long #define ull unsigned long...