思路:

考虑不存在三角形的情况:也就是说,任意选择三个数,总有一个最大的数不小于剩下两个数的总和.

我们想到一个的数列:斐波那契数列.

那么权值均在题目给定数据范围内的数列有多长?至多有\(log(Max)\)项.

如果超过这些项,就会在两个数之间插入某一个数,那么这三个数就是必定满足三角形条件的.(有点意识流)

总之如果总共有不超过\(log(Max)\)个数暴力判定,否则直接输出\(Y\).

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
#define N 100010
int head[N],next[N<<1],end[N<<1];
inline void addedge(int a,int b){static int q=1;end[q]=b,next[q]=head[a],head[a]=q++;}
inline void make(int a,int b){addedge(a,b),addedge(b,a);}
 
int w[N];
 
int pa[N][16],dep[N];
inline void dfs(int x,int fa){
    for(int j=head[x];j;j=next[j])if(end[j]!=fa)dep[end[j]]=dep[x]+1,pa[end[j]][0]=x,dfs(end[j],x);
}
int lca(int x,int y){
    if(dep[x]<dep[y])swap(x,y);
    for(int i=15;i>=0;--i)if(dep[pa[x][i]]>=dep[y])x=pa[x][i];
    if(x==y)return x;
    for(int i=15;i>=0;--i)if(pa[x][i]!=pa[y][i])x=pa[x][i],y=pa[y][i];
    return pa[x][0];
}
 
int seq[51],id;
 
inline bool judge(int a,int b,int c){
    long long A=a,B=b,C=c;
    return A+B>C&&B+C>A&&A+C>B;
}
 
int main(){
    int n,m;scanf("%d%d",&n,&m);register int i,j,k;for(i=1;i<=n;++i)scanf("%d",&w[i]);
     
    int a,b;for(i=1;i<n;++i)scanf("%d%d",&a,&b),make(a,b);
     
    dep[1]=1,dfs(1,-1);
    for(j=1;j<=15;++j)for(i=1;i<=n;++i)pa[i][j]=pa[pa[i][j-1]][j-1];
     
    int t;
    while(m--){
        scanf("%d%d%d",&t,&a,&b);
        if(t==0){
            int Lca=lca(a,b),nums=dep[a]+dep[b]-2*dep[Lca]+1;
            if(nums<=40){
                for(id=0;a!=Lca;a=pa[a][0])seq[++id]=w[a];
                for(;b!=Lca;b=pa[b][0])seq[++id]=w[b];
                seq[++id]=w[Lca];
                bool ok=0;
                for(i=1;i<=id;++i)for(j=i+1;j<=id;++j)for(k=j+1;k<=id;++k)if(judge(seq[i],seq[j],seq[k]))ok=1;
                if(ok)puts("Y");else puts("N");
            }else puts("Y");
        }else w[a]=b;
    }
     
    return 0;
}

思路:

令\(x\)是一个可行答案,有\(x^2\%n=1\),即\((x-1)(x+1)=kn(k\in{Z})\).

显然我们可以令\(x-1=k_1n_1,x+1=k_2n_2,k=k_1k_2,n=n_1n_2\).(交换一下也是可以的)

那么我们就可以枚举所有的\(n_1\),看一看他能够表达出的\(x+1\)或是\(x-1\)是不是一个合法答案.我们用一个哈希表来支持插入.最后输出即可.

但是我们发现枚举所有的\(n_1\)(n的约数)显然是要超时的.因此我们只枚举\(n_1\geq{\sqrt{n}}\)的\(n_1\).这样单次枚举的复杂度为\(\sqrt{n}\),而且这样的约数非常少,这样就可以通过了.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
using namespace std;
 
static const int mod=(1e5)+7;
struct HashSet{
    int head[mod],v[200010],next[200010],ind;
    void reset(){ind=0,memset(head,-1,sizeof head);}
    void insert(int x){
        int ins=x%mod;
        for(int j=head[ins];j!=-1;j=next[j])if(v[j]==x)return;
        v[ind]=x,next[ind]=head[ins],head[ins]=ind++;
    }
}S;
 
int n;
void Solve(int x){
    for(int d=x;d<n-1;d+=x)if((long long)d*(d+2)%n==0)S.insert(d+1);
    for(int d=x;d<=n;d+=x)if(d-2>=1&&(long long)d*(d-2)%n==0)S.insert(d-1);
}
int main(){
    scanf("%d",&n);
    if(n==1)puts("NONE");
    else{
        S.reset(),S.insert(1);
        for(int i=1;i*i<=n;++i)if(n%i==0)Solve(max(i,n/i));
        sort(S.v,S.v+S.ind);
        for(int i=0;i<S.ind;++i)printf("%d\n",S.v[i]);
    }
     
    return 0;
}

思路:

首先我们需要知道欧拉函数的计算方法:

\[n=p_1^{q_1}p_2^{q_2}...p_m^{q_m}\rightarrow\phi(n)=n\frac{p_1-1}{p_1}\frac{p_2-1}{p_2}...\frac{p_m-1}{p_m}\]

\[\phi(n)=p_1^{q_1}\frac{p_1-1}{p_1}p_2^{q_2}\frac{p_2-1}{p_2}...p_m^{q_m}\frac{p_m-1}{p_m}\]

这证明我们可以将所有的质因数分开考虑.

我们对于所有质因数计算其贡献,然后乘到一起.(这东西维护一个前缀和就行了)

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
 
#define N 10000010
int p[N/10],ins[N],cnt;bool notp[N];vector<int>v[N/10];
inline void pre(){
    register int i,j;
    for(i=2;i<=10000000;++i){
        if(!notp[i])p[++cnt]=i,ins[i]=cnt;
        for(j=1;j<=cnt&&i*p[j]<=10000000;++j){
            notp[i*p[j]]=1;
            if(i%p[j]==0)break;
        }
    }
}
 
static const int mod=(1e9)+7;
inline int ksm(int x,int y){
    int t=x,res=1;for(;y;y>>=1,t=(long long)t*t%mod)if(y&1)res=(long long)res*t%mod;return res;
}
inline int inv(int x){
    return ksm(x,mod-2);
}
inline void inc(int&x,int y){
    if((x+=y)>=mod)x-=mod;
}
 
int seq[1000010],num;vector<int>vv[1000010];
 
int pref[40];
 
int main(){ 
    pre();
     
    int n;scanf("%d",&n);register int i,j,k;
    int x,nowadd;
    while(n--){
        scanf("%d",&x);if(x==1)continue;
        for(i=1;i<=cnt&&p[i]*p[i]<=x;++i){
            nowadd=0;while(x%p[i]==0)++nowadd,x/=p[i];
            if(nowadd)v[i].push_back(nowadd);
        }if(x)v[ins[x]].push_back(1);
    }
     
    for(i=1;i<=cnt;++i)if((int)v[i].size()!=0){
        seq[++num]=p[i];
        for(j=0;j<(int)v[i].size();++j)vv[num].push_back(v[i][j]);
    }
     
    if(num==0)puts("1");
    else{
        int res=1,Mx,mi,tans;
        for(k=1;k<=num;++k){
            for(Mx=0,i=0;i<vv[k].size();++i)Mx=max(Mx,vv[k][i]);
            for(pref[0]=1,mi=seq[k],i=1;i<=Mx;++i,mi=(long long)mi*seq[k]%mod)inc(pref[i]=pref[i-1],mi);
            for(tans=1,i=0;i<vv[k].size();++i)tans=(long long)tans*pref[vv[k][i]]%mod;
            tans=(long long)(tans+mod-1)*(seq[k]-1)%mod;
            tans=(long long)tans*inv(seq[k])%mod;
            res=(long long)res*(tans+1)%mod;
        }
        printf("%d",res);
    }
     
    return 0;
}

思路:

对于一个数列\(f_0,f_1,f_2,...\),我们可以对应的构造一个多项式函数\(f_0+f_1{x}+f_2{x^2}+...\),也即若我们可以知道函数的\(x^n\)项系数,就能知道\(f_n\).

一眼看起来并没有什么用处,实际上有的多项式函数可以化为十分简洁的形式.

例如\(f_0=f_1=f_2=...=1\),其对应的多项式函数为\(1+x+x^2+x^3+...\).

由于我们只在意式子的"型",因此可以利用方便的等比数列来表示:

\[\frac{1-x^{\infty}}{1-x}\]

若\(|x|<1\),则可以化为:

\[\frac{1}{1-x}\]

事实上我们不必在意\(x\)的范围,仅仅是看重形式便可以了.

对于这道题目的计数问题,我们仅需搞出所有限制的多项式,然后将它们相乘.

最终经过一些化简得到:

\[\frac{x}{(1-x)^4}\]

接下来有一种处理方法就是暴力泰勒展开(就是无限求导),感觉不可能找到规律(至少我是不会).

然后又一种方法就是再进行变形:

\[x(1+x+x^2+...)^4\]

求上式的\(x^n\)次项的系数.于是变成简单的组合数问题.

#include<cstdio>
#include<cstring>
#include<cctype>
#include<climits>
#include<iostream>
#include<algorithm>
using namespace std;

char s[510];
int main(){
	scanf("%s",s);int len=strlen(s);register int i,j;
	int t=0;for(i=0;i<len;++i)t=(t*10+s[i]-'0')%10007;
	int res=t;res=res*(t+1)%10007,res=res*(t+2)%10007;
	res=res*1668%10007;
	printf("%d",res);
	return 0;
}