SGU 100
题意：
普通的a+b
#include<bits/stdc++.h> #define de(x) cout<<#x<<"="<<x<<endl; #define dd(x) cout<<#x<<"="<<x<<" "; #define rep(i,a,b) for(int i=a;i<(b);++i) #define repd(i,a,b) for(int i=a;i>=(b);--i) #define repp(i,a,b,t) for(int i=a;i<(b);i+=t) #define ll long long #define mt(a,b) memset(a,b,sizeof(a)) #define fi first #define se second #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3f #define pii pair<int,int> #define pdd pair<double,double> #define pdi pair<double,int> #define mp(u,v) make_pair(u,v) #define sz(a) (int)a.size() #define ull unsigned long long #define ll long long #define pb push_back #define PI acos(-1.0) #define qc std::ios::sync_with_stdio(false) #define db double #define all(a) a.begin(),a.end() const int mod = 1e9+7; const int maxn = 2e5+5; const double eps = 1e-6; using namespace std; bool eq(const db &a, const db &b) { return fabs(a - b) < eps; } bool ls(const db &a, const db &b) { return a + eps < b; } bool le(const db &a, const db &b) { return eq(a, b) || ls(a, b); } ll gcd(ll a,ll b) { return a==0?b:gcd(b%a,a); }; ll lcm(ll a,ll b) { return a/gcd(a,b)*b; } ll kpow(ll a,ll b) {ll res=1;a%=mod; if(b<0) return 1; for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll read(){ ll x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } //inv[1]=1; //for(int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod; int main(){ int a,b; cin>>a>>b; cout<<a+b<<endl; return 0; }
收获：无
SGU 101
题意：求一条欧拉通路，并记录路径
收获：
欧拉回路：1: 图G是连通的，不能有孤立点存在。
2: 对于无向图来说度数为奇数的点个数为0;对于有向图来说每个点的入度必须等于出度。
欧拉通路：1: 图G是连通的，无孤立点存在。
2: 对于无向图来说，度数为奇数的的点可以有2个或者0个，并且这两个奇点其中一个为起点另外一个为终点。对于有向图来说，可以存在两个点，其入度不等于出度，其中一个入度比出度大1，为路径的起点；另外一个出度比入度大1，为路径的终点。
欧拉回路：从一个点出发，经过图中的所以边且只经过一次，最终回到起点。
欧拉通路：就是欧拉回路可以不回到起点
回路就相当于通路的起点和终点是重合的
Euler算法：（个人见解），算法本质就是dfs起点，然后回溯的时候记录边，然后倒序输出，为什么倒序呢，可以画图比较好理解，最早回溯的一定是终点的边，因为通路其实就是一笔画，那你出现回溯的话，就说明接下来已经走不通了，就是画不下去了，也就是终点，同理第二次回溯的记录边
也就是倒二次的路
#include<bits/stdc++.h> #define de(x) cout<<#x<<"="<<x<<endl; #define dd(x) cout<<#x<<"="<<x<<" "; #define rep(i,a,b) for(int i=a;i<(b);++i) #define repd(i,a,b) for(int i=a;i>=(b);--i) #define repp(i,a,b,t) for(int i=a;i<(b);i+=t) #define ll long long #define mt(a,b) memset(a,b,sizeof(a)) #define fi first #define se second #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3f #define pii pair<int,int> #define pdd pair<double,double> #define pdi pair<double,int> #define mp(u,v) make_pair(u,v) #define sz(a) (int)a.size() #define ull unsigned long long #define ll long long #define pb push_back #define PI acos(-1.0) #define qc std::ios::sync_with_stdio(false) #define db double #define all(a) a.begin(),a.end() const int mod = 1e9+7; const int maxn = 1e2+5; const double eps = 1e-6; using namespace std; bool eq(const db &a, const db &b) { return fabs(a - b) < eps; } bool ls(const db &a, const db &b) { return a + eps < b; } bool le(const db &a, const db &b) { return eq(a, b) || ls(a, b); } ll gcd(ll a,ll b) { return a==0?b:gcd(b%a,a); }; ll lcm(ll a,ll b) { return a/gcd(a,b)*b; } ll kpow(ll a,ll b) {ll res=1;a%=mod; if(b<0) return 1; for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll read(){ ll x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } //inv[1]=1; //for(int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod; int n,tot; struct edge{ int v,nt,id; }e[maxn<<1]; bool vis[maxn<<1]; int pre[8],in[8]; void init(){ tot=0;mt(pre,-1);mt(in,0);mt(vis,false); } void add(int u,int v,int id){ e[tot].v=v;e[tot].nt=pre[u];e[tot].id=id;pre[u]=tot++; e[tot].v=u;e[tot].nt=pre[v];e[tot].id=id;pre[v]=tot++; } vector<int> ans; void Euler(int u){ for(int i=pre[u];~i;i=e[i].nt){ int v=e[i].v; if(!vis[i]){ vis[i]=vis[i^1]=true; Euler(v); ans.pb(i); } } } int main(){ init(); scanf("%d",&n); int odd = 0,st; int u,v; rep(i,1,n+1) { scanf("%d%d",&u,&v);add(u,v,i);in[u]++;in[v]++;st = u; } rep(i,0,7) if(in[i]&1) odd++,st=i; if(!odd||odd==2) { Euler(st); if(sz(ans)!=n) printf("No solution "); else repd(i,sz(ans)-1,0) printf("%d %c ",e[ans[i]].id,(ans[i]&1)?'-':'+'); } else printf("No solution "); return 0; }
SGU 102
题意：求小于N的并且和N互质的数字的数量
收获：
就是求phi函数：
#include<bits/stdc++.h> #define de(x) cout<<#x<<"="<<x<<endl; #define dd(x) cout<<#x<<"="<<x<<" "; #define rep(i,a,b) for(int i=a;i<(b);++i) #define repd(i,a,b) for(int i=a;i>=(b);--i) #define repp(i,a,b,t) for(int i=a;i<(b);i+=t) #define ll long long #define mt(a,b) memset(a,b,sizeof(a)) #define fi first #define se second #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3f #define pii pair<int,int> #define pdd pair<double,double> #define pdi pair<double,int> #define mp(u,v) make_pair(u,v) #define sz(a) (int)a.size() #define ull unsigned long long #define ll long long #define pb push_back #define PI acos(-1.0) #define qc std::ios::sync_with_stdio(false) #define db double #define all(a) a.begin(),a.end() const int mod = 1e9+7; const int maxn = 1e2+5; const double eps = 1e-6; using namespace std; bool eq(const db &a, const db &b) { return fabs(a - b) < eps; } bool ls(const db &a, const db &b) { return a + eps < b; } bool le(const db &a, const db &b) { return eq(a, b) || ls(a, b); } ll gcd(ll a,ll b) { return a==0?b:gcd(b%a,a); }; ll lcm(ll a,ll b) { return a/gcd(a,b)*b; } ll kpow(ll a,ll b) {ll res=1;a%=mod; if(b<0) return 1; for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;} ll read(){ ll x=0,f=1;char ch=getchar(); while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } //inv[1]=1; //for(int i=2;i<=n;i++) inv[i]=(mod-mod/i)*inv[mod%i]%mod; int euler_phi(int n){ int res = n; int m = (int)sqrt(n); rep(i,2,m+1) if(n % i == 0){ res = res / i * (i-1); while(n % i == 0) n /= i; } if(n > 1) res = res / n * (n-1); return res; } //下面是预处理phi函数的板子 //void euler_phi() //{ // for(int i = 1; i < N; i++) phi[i] = i; // for(int i = 2; i < N; i++) // if(phi[i] == i) //成立说明i是素数 // for(int j = i; j < N; j += i) //j要从i开始，这样可以处理素数的情况 // phi[j] = phi[j] / i * (i-1); //} //下面是关于欧拉函数的一些简单性质 //任意一个大于1的正整数，都可以写成一系列质数的积,即n=(p1^k1)*(p2^k2)*...*(pr^kr) //1. 当p为素数时,phi(p^k)=p^k-p^(k-1)=(p^k)*(1-1/p) (k>=1) //2. phi(1) = 1 //3. 如果n=p*q且gcd(p,q)==1,则phi(n)=phi(p)*phi(q) //4. 因为n=(p1^k1)*(p2^k2)*...*(pr^kr),所以phi(n)=phi(p1^k1)*...*phi(pr^kr) int main(){ int n; scanf("%d",&n); printf("%d ",euler_phi(n)); }