题意：一个圆上有n个等分点，现在从一个点出发，指定k，不停地隔k个点连边（样例请看link），问有多少种不同的方法，使得所有的点都被连起来。两种情况是一样的，当且仅当他们旋转若干角度以后是一样的。
tags：首先要运用一下数论知识，很容易就可以得出只有和n互质的k才是合法的。然后发现，k画出的图可以通过旋转得到n-k的图，而(n,k)=1 <-> (n,n-k)=1，所以答案为(phi(n) + 1)/2。Phi为欧拉函数。
#includeusing namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define rep(i,a,b) for (int i=a;i<=b;i++)#define per(i,b,a) for (int i=b;i>=a;i--)#define mes(a,b) memset(a,b,sizeof(a))#define INF 0x3f3f3f3ftypedef long long ll;const int N = 200005;ll getphi(ll n){ ll ans=n; for(ll i=2; i*i<=n; ++i) if(n%i==0) { ans= ans/i*(i-1); while(n%i==0) n/=i; } if(n>1) ans= ans/n*(n-1); return ans;}int main(){ ll n; for(; scanf("%lld", &n)>0; ) { printf("%lld\n", getphi(n)/2); } return 0;}
题意：给定n个字符串，统计字符串(s1, s2)的对数，使得s1的字典序比s2的字典序要大，s1反一反（abc->cba，记为s1’）比s2’的字典序要小。
tags：按字符串的字典序排序，从小到大枚举，假设现在考虑到了字符串s1，那么我们已经处理过了所有字典序<s1的字符串s2，我们关心的是这些字符串中满足s1’<s2’的s2的数目，可以完美地用trie树解决。
#includeusing namespace std;#pragma comment(linker, "/STACK:102400000,102400000")#define rep(i,a,b) for (int i=a;i<=b;i++)#define per(i,b,a) for (int i=b;i>=a;i--)#define mes(a,b) memset(a,b,sizeof(a))#define INF 0x3f3f3f3ftypedef long long ll;const int N = 1000005;int n, f[N], a[N][26], cnt;string s[N];void insert_rev_trie(string str){ int len=str.length(), now=0; for(int i=len-1; i>=0; --i) { if(a[now][str[i]-'a']==0) a[now][str[i]-'a']=++cnt; now=a[now][str[i]-'a']; ++f[now]; }}int calc_rev_trie(string str){ int len=str.length(), now=0, sum=0; for(int i=len-1; i>=0; --i) { for(int j=str[i]-'a'+1; j<26; ++j) sum += f[a[now][j]]; now=a[now][str[i]-'a']; } for(int j=0; j<26; ++j) sum += f[a[now][j]]; return sum;}int main(){ cnt=0; mes(f, 0); mes(a, 0); scanf("%d", &n); rep(i,1,n) cin>>s[i]; sort(s+1, s+1+n); ll ans=0; rep(i,1,n) insert_rev_trie(s[i]), ans += calc_rev_trie(s[i]); printf("%lld\n", ans); return 0;}/*2loptakugla4lovanovacaronsunce14branimirvladimirtomkruzbredpitzemljanijeravnaplocakojezapaliozito*/