A.Reciprocal cycles
求小数循环节的方法
#include <iostream> #include <cstdio> #include <cstring> #include <string> using namespace std; const int MAXN = 1e4+100; int a[MAXN]; int c[MAXN]; int mark[MAXN]; int fun(int x){ int h,d,id=1,sum=0; memset(c,0,sizeof c); memset(mark,0,sizeof mark); d = 1; c[1] = mark[1] = 1; while(d!=0){ h = d*10%x; id++; mark[h]++; d = h; //cout<<id<<" "; if(mark[h]>1){ sum = id-c[h]; break; } c[h] = id; //cout<<h<<" "<<endl; } if(d==0)sum = 0; return sum; } int main() { //cout<<fun(9)<<endl; int mmax = 0; a[1] = 1; int pre = -1; for(int i=2;i<MAXN;i++){ int x = fun(i); //mmax = max(mmax,x); //a[i] = mmax; if(mmax<x){ pre = i; mmax = x; } a[i] = pre; } //cout<<mmax<<endl; int T; scanf("%d",&T); while(T--){ int n; scanf("%d",&n); printf("%d ",a[n-1]); } //cout << "Hello world!" << endl; return 0; }
C.Number spiral diagonals
主要推公式比较复杂
没草稿纸 推了 好久好久
学习了了一个公式
1*2+2*3+3*4+..n*(n+1) = n*(n+1)*(n+2)/3
#include <cstdio> #include <iostream> #include <cmath> #include <string> #include <cstring> using namespace std; typedef long long ll; const ll MOD = 1e9+7; ll mult(ll a,ll b){ ll ans = 0; a %= MOD; while(b){ if(b&1){ ans += a; ans %= MOD; b--; } a *= 2; b>>=1; a %= MOD; } return ans; } ll qb(ll a,ll b){ ll ans = 1; a %= MOD; while(b){ if(b&1){ ans = mult(ans,a); b--; } a = mult(a,a); b>>=1; } return ans; } int main(){ //cout<<mult(3,0); //cout<<mult(4,2); ll x = qb(3,MOD-2); //cout<<x<<endl; //cout<<12*x%MOD<<endl; //cout<<11*x*3%MOD<<endl; // cout<<3*x%MOD<<endl; int T; scanf("%d",&T); while(T--){ ll n; scanf("%lld",&n); n = n/2+1; //ll ans = 1+24*(n-1)%MOD+10*(n-1)%MOD*(n-2)%MOD+16*(n-2)%MOD*(n-1)%MOD*n%MOD*x%MOD; //ll ans = 16*(n-2)%MOD*(n-1)%MOD*n%MOD*x%MOD; ll ans = 1+mult(24,n-1)+mult(mult(10,n-1),n-2)+mult(16,mult(n-2,mult(n-1,mult(n,x)))); ans %= MOD; //ll ans = (1LL)*10*(n-1)%MOD*(n-2)%MOD; //ans %= MOD; cout<<ans<<endl; //printf("%lld ",x); } return 0; }
E.Distinct powers
题意比较清楚就不说了，这题让我学习set的用法，虽然并没有什么用
回家之后一直想，算是找到了比较简单的方法，但是还是错了第10组数据...
这题的通过率只有30%多，算是非常低的啦
现在在问出题者索求数据，希望可以给我吧qaq
还是贴一下知错了一组数据的代码
有毒 我昨晚在github终于找到一份别人的代码，然后对比数据，发现就是1000的时候才会出错，而且只有一组，(int)log(1000)/log(10)<3你敢信。。。。然后(int)log(10000)/log(10)=4，你坑谁呀。。。
最后发现log(x)+0.000001 pow(10,x)+0.000001 灰常有用
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <cstring> using namespace std; typedef long long ll; const int MAXN = 3e6+100; int mark[MAXN]; ll a[50]; int main() { int n; scanf("%d",&n); int x = log2(n*1.0); //cout<<x<<endl; for(int i=1;i<=x;i++){ ll sum = 0,t = 2*i; for(int j=1;j<n;j++){ if(!mark[t]){ sum++; mark[t] = 1; } t = t+i; } // cout<<t<<" "; a[i] = sum; } // cout<<endl; //cout<<x<<endl; //for(int i=1;i<=x;i++)cout<<a[i]<<" "<<endl; memset(mark,0,sizeof mark); ll ans = 0; for(ll i=2;i<=n;i++){ if(!mark[i]){ double t = log(n*1.0)/log(i*1.0); int tt = (int)(t+0.00001); //cout<<t<<" "<<tt<<endl; for(ll j=1;j<=tt;j++)ans+= a[j]; for(ll j=i*i;j<=n;j=j*i)mark[j] = 1; } //cout<<ans<<" "; } //cout<<endl; cout<<ans<<endl; //cout << "Hello world!" << endl; return 0; }
F: Coin sums
最烦这种枚举题目了，网上找到了一个很棒的题解
https://www.thanassis.space/euler31.html
仔细想想，还是比较简单的状态转移的
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include <set> using namespace std; typedef long long ll; const int MOD = 1e9+7; const int MAXN = 1e5; ll dp[MAXN+100][8]; int a[8] = {1,2,5,10,20,50,100,200}; int main() { /* Enter your code here. Read input from STDIN. Print output to STDOUT */ for(int i=0;i<8;i++)dp[0][i] = 1; for(int i=1;i<=MAXN;i++)dp[i][0] = 1; for(int i=1;i<=MAXN;i++){ for(int j=1;j<8;j++){ if(i>=a[j]){ dp[i][j] = dp[i][j-1]; dp[i][j] += dp[i-a[j]][j]; // 到达[i,j]只有两条路径 dp[i][j] %= MOD; } else{ dp[i][j] = dp[i][j-1]; dp[i][j] %= MOD; } } } /*for(int i=1;i<=6;i++){ for(int j=0;j<=5;j++){ cout<<dp[i][j]<<" "; } cout<<endl; }*/ int T; scanf("%d",&T); while(T--){ int n; scanf("%d",&n); cout<<dp[n][7]<<endl; } return 0; }
G.Pandigital products
看了一下别人的代码，其实这个程序写的挺渣的
不过打表超级暴力的思想可以借鉴一下，有些时候想暴力也不知道怎么简化。。。
其实这个代码跑了150s，看看思想就好了呵呵。。。
#include <cstdio> #include <iostream> #include <string> #include <cstring> #include <cmath> #include <set> #include <sstream> using namespace std; int a[10]; set<int>st; char ts[100]; bool ispandigit(int n,int len){ int mark[10]; memset(mark,0,sizeof mark); if(len!=n)return false; for(int i=0;i<len;i++){ int t = int(ts[i]-'0'); if(t>n||t==0||mark[t]){ return false; } mark[t] = 1; } return true; } int main(){ for(int i=4;i<=9;i++){ //if(i!=4)continue; int t = pow(10,i/2); //cout<<t<<endl; st.clear(); int sum = 0; for(int j=1;j<t;j++){ for(int k=j+1;k<t;k++){ int ans = j*k; int top = 0; sprintf(ts,"%d",j); //top = strlen(ts); top = strlen(ts); sprintf(ts+top,"%d",k); top = strlen(ts); sprintf(ts+top,"%d",ans); //ts[++top] = ' '; top = strlen(ts); //printf("%s ",ts); if(ispandigit(i,top)){ if(st.find(ans)==st.end()){ sum+= ans; st.insert(ans); //cout<<j<<" "<<k<<" "<<ans<<endl; } } } } a[i] = sum; } //cout<<endl; for(int i=4;i<=9;i++){ cout<<a[i]<<" "; } // cout<<endl; return 0; }
N.Integer right triangles
题意：求一个数最多能被拆成几个勾股数
学习了原始勾股数的性质
a = i*i-j*j
b = 2*i*j
c = i*i+j*j
且a>0&&gcd(i,j) = 1
#include <cmath> #include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include <string> using namespace std; const int MAXN = 5e6+100; int ta[MAXN],ans[MAXN]; int gcd(int a,int b){ if(b==0)return a; return gcd(b,a%b); } int main(){ for(int i=1;;i++){ if(2*i*i+2*i>MAXN)break; for(int j=1;j<i;j++){ if((i-j)%2==1&&gcd(i,j)==1){ for(int k=1;;k++){ int a = k*(i*i-j*j); int b = k*2*i*j; int c = k*(i*i+j*j); if(a<=0)break; if(a+b+c>=MAXN)break; ta[a+b+c]++; } } } } //cout<<"hahha"<<endl; int mmax = -1; for(int i=1;i<MAXN;i++){ if(ta[i]>mmax){ans[i] = i;mmax = ta[i];} else ans[i] = ans[i-1]; } int T; scanf("%d",&T); while(T--){ int n; scanf("%d",&n); cout<<ans[n]<<endl; } return 0; }