Gym 101028J 100541D

Gym 100499I

这题当理解题意的时候就出现一个难题，循环小数怎么转化为分数，果断百度下。

普及知识：1,纯循环小数:小数点后有几位数,分母就有几个9,分子为一个循环节.如:0.345(345循环)=345／999 该化简就化简即可.2,混循环小数:小数点后到第一个循环减去非循环小数部分作为分子,循环节内有几位数,分母就有几个9,然后接着写几个0,0的个数为第一个循环节前面非循环小数的位数.如:0.0231(31循环)=(0231-02)/9900 需要化简再化简.

题意：循环小数0.16666....输入的时候可以0.1（6）和0.16666（6）和0.166（66）这样表示括号表示以括号里的数字循环，当然输入的小数也可能不是循环小数，输出分数表示。

思路：分三种表示，第一种是'.'前面的数然后就是'('和'.'之前的数还有'('之后的数，将他们分离出来处理即可。

代码如下：

#include<iostream>
#include<algorithm>
#include<string.h>
#include<cstdio>
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
char str[20];
LL gcd(LL a,LL b)
{
  if(b==0) return a;
  return gcd(b,a%b);
}
int main()
{
  int t;int Case=1;
  scanf("%d",&t);
  while(t--)
  {
    scanf("%s",&str);
    int len=strlen(str);
    LL a=0,b=0,c=0;int flag=0,x=0;
    printf("Case #%d: ",Case++);
    int i;
    for(i=0;i<len;i++)
    {
      if(str[i]!='.')
      {
        a=a*10+(str[i]-'0');
      }
      else
      {
        flag=1;x=i;
        break;
      }
    }
    if(flag==0)
    {
      printf("%lld/1\n",a);continue;
    }
    i++;LL ans=1;int j;
    for(;i<len;i++)
    {
      if(str[i]!='(')
      {
        b=b*10+(str[i]-'0');ans*=10;
      }
      else break;
    }
    if(str[i]=='\0')
    {
      LL cnt=gcd(b,ans);
      b/=cnt;ans/=cnt;
      b+=ans*a;
      printf("%lld/%lld\n",b,ans);continue;
    }
    i++;LL pos=1;
    for(;i<len;i++)
    {
      if(str[i]!=')')
      {
        c=c*10+str[i]-'0';pos*=10;
      }
      else break;
    }
    pos-=1;
    LL sum=b*pos+c,res=ans*pos;
    LL tt=gcd(sum,res);
    sum/=tt;res/=tt;sum+=res*a;
    printf("%lld/%lld\n",sum,res);
  }
}

题意：给你两个数x和k，有k次操作每次操作为x=x+xmod100，求最后输出。

思路：由于数据量很大那么不能暴力做了，考虑的第一件事就是找出规律，最后发现不是简单固定的规律，由于是mod100那么只考虑十为和个位数那么当这十位数*2多次之后会出现循环，但由于是0~99每个数循环不一样，那就只能开个数组记录位置当发现出现相同数的时候就找到循环的长度并记录循环之前的长度，这样就可以直接用k减去之前的长度然后除以循环的长度得到的余数在处理。

代码如下：

#include<iostream>
#include<algorithm>
#include<string.h>
#include<cstdio>
using namespace std;
typedef long long LL;
#define INF 0x3f3f3f3f
LL a[1005],b[1005];
int main()
{
  int t;LL n,k;
   scanf("%d",&t);
    while(t--)
    {
      scanf("%lld%lld",&n,&k);
      memset(a,-1,sizeof(a));
      memset(b,0,sizeof(b));
      LL sum=n,ans=0,i;n-=(n/100)*100;
      for(i=1;i<=k;i++)
      {
        ans+=n;
        if(a[n]!=-1)
        {
          ans+=((k-i)/(i-b[n]))*(ans-a[n]);
          i+=((k-i)/(i-b[n]))*(i-b[n]);
          n*=2;n%=100;break;
        }
        a[n]=ans;b[n]=i;//n*=2;n%=100;
        n*=2;n-=(n/100)*100;
      }
      for(;i<k;i++)
      {
        ans+=n;n*=2;n-=(n/100)*100;
      }
      printf("%lld\n",sum+ans);
    }
}