T1（Loj6083）：
给定L,R，求在[L,R]区间的数的所有因子的最高位数码出现的次数。比如A=17*23，A对1的贡献和对2的贡献均为1。L<=R<=10^9。
题解：
直接枚举L,R算因数显然不可行，既然是每个因子对应几个贡献，我们可以考虑枚举每个因子计算答案。
由于1-9是分开计数的，那么可以将所有最高位分别为1-9的因子归到一起计算。
按数位dp的思想，分别计算[1,R]和[1,L-1]内最高位为i的满足条件的因子个数，相减即可。
易知首位为i的k位数取值范围为[i*10^k，(i+1)*10^k-1），记作[l，r]。
朴素算法是从l开始枚举每个数i，设当前上界为n，i对答案的贡献是n/i（i分之n下取整）。
（显然当i作为i，2i，3i，……，(n/i)*i的约数时有贡献，(n/i)+1)*i超出上界）
那么理论复杂度还是O(10^9)的，但考场上写这个居然有70pts……
（不过10组全是极限数据出题人可能会被D……）
重要的是，我们发现如果k较大时，有很多数的贡献其实是一样的，也就是n/x==n/y。
那么如果将贡献值相同的数一并计算，就能将O（n）的复杂度降成O（n/min(i)），堪称奇迹。
对于某一个i，满足n/j==n/i的最大的j显然是n/(n/i)。[可以由下取整的特点：n/k是整数中最后一个乘上k不超过n的数得知]
那么答案累加(j-i+1）*(n/i)即可。
代码：
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> using namespace std; #define MAXN 100005 #define MAXM 500005 #define INF 0x7fffffff #define mod 1000000007 #define ll long long inline ll read(){ ll x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } inline ll calc(ll num,ll l,ll r){ ll ans=0,x=l,y=0; while(x<=r){ y=min(r,num/(num/x)); ans+=(y-x+1)*(num/x); x=y+1; } return ans; } inline ll solve(ll num,ll x){ ll y=1,ans=0; while(x<=num){ ans+=calc(num,x,min(x+y-1,num)); x*=10,y*=10; } return ans; } int main(){ ll L=read(),R=read(); for(ll i=1;i<=9;i++) printf("%lld ",solve(R,i)-solve(L-1,i)); return 0; }
T2（Loj2043）：
已知平面下的N个点坐标，求欧氏距离下的k远点对。
题解：
据说是kd-tree，不会……
T3（Loj6159）：
给定一棵N个点的树，每个点有点权A[i]，求最长的gcd不等于1的链。N<=10^5,A[i]<=10^9。
题解：
考虑暴力枚举各个点的所有质因数后dfs，每遍历一个质因数后不再遍历它，
显然每个点被遍历的次数等于它的质因数个数也就是logA[i]，复杂度O（NlogA[i]）。
然后我就T了。原因是我把素数表打的太大。
设A[i]=p1^a1*p2^a2*……*pn^an。显然不会出现两个>=sqrt(10^9)的p[i]，
所以素数表打到sqrt(10^9)，分解完质因数如果x还不等于1则剩余的那个数就当一个大素数处理一遍。
代码：
#include<algorithm> #include<iostream> #include<cstring> #include<cstdio> #include<vector> using namespace std; #define MAXN 100005 #define MAXM 505 #define INF 0x7fffffff #define ll long long int hd[MAXN],to[MAXN<<1],nxt[MAXN<<1],cnt; int A[MAXN],p[MAXN],num; bool isp[MAXN],vis[MAXN]; int dp[MAXN];vector<int> v[MAXN]; inline int read(){ int x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } inline void addedge(int u,int v){ to[++cnt]=v,nxt[cnt]=hd[u]; hd[u]=cnt;return; } inline void init(){ for(int i=2;i<=MAXN;i++){ if(!isp[i]) isp[i]=1,p[++num]=i; for(int j=1;j<=num && p[j]*i<=MAXN;j++) {isp[p[j]*i]=1;if(i%p[j]==0) break;} }return; } inline int dfs(int u,int fa,int x){ int maxans=0,mx=0,cx=0; for(int i=hd[u];i;i=nxt[i]){ int v=to[i]; if(v==fa) continue; if(A[v]%x==0){ maxans=max(maxans,dfs(v,u,x)); if(dp[v]>mx) cx=mx,mx=dp[v]; else if(dp[v]>cx) cx=dp[v]; } } dp[u]=1+mx;return max(maxans,1+mx+cx); } int main(){ //freopen("gtree3.in","r",stdin); //freopen("mine.out","w",stdout); int N=read(),ans=0;init(); for(int i=1;i<=N-1;i++){ int u=read(),v=read(); addedge(u,v);addedge(v,u); } for(int i=1;i<=N;i++){ A[i]=read();int x=A[i]; for(int j=1;(j<=num)&&(p[j]*p[j]<=A[i]);j++){ if(x%p[j]==0) v[i].push_back(p[j]); while(x%p[j]==0) x/=p[j]; if(x==1) break; } if(x>1) v[i].push_back(x); } for(int i=1;i<=N;i++) for(int j=0;j<v[i].size();j++) if(!vis[v[i][j]]) ans=max(ans,dfs(i,0,v[i][j])),vis[v[i][j]]=1; printf("%lld ",ans); return 0; }